본문 바로가기

정렬5

퀵 정렬(Quick sort)_개념/시간복잡도/Unstable/In-place 퀵 정렬에 대한 이해 - 퀵 정렬이란, 피벗을 설정하여 이를 올바른 위치로 이동시킨 뒤 나머지 원소들을 두 개의 배열로 분할하여 재귀적으로 정렬시키는 알고리즘이다. - 합병정렬과 달리, 배열이 불균등하게 분할된다.(운이 좋으면, 균등하게 분할 될 수도 있다.) 코드를 먼저 보면, void quickSort(int st, int en) { if (en 2022. 2. 19.
합병정렬(Merge sort)_개념/시간복잡도/Stable/Not In-place 합병 정렬에 대한 이해 - 합병정렬이란, 하나의 배열을 두개의 균등한 배열로 분할하고 분할된 배열을 각각 정렬한 다음, 이를 다시 합하여 정렬을 완성하는 알고리즘이다. - 합병정렬은 분할 정복의 일종으로, 하나의 큰 문제를 두개의 작은 문제로 분할하여 해결한 다음, 결과를 모아서 문제를 완전히 해결하는 전략이다. 코드를 먼저 살펴보면, void mergeSort(int st, int en) { if (en == st+1) return ; int mid = (st+en)/2; mergeSort(st, mid); //arr[st:en]을 두개의 균등한 배열로 분할하여 각각 정렬 mergeSort(mid, en); merge(st, en); //정렬된 두개의 배열 arr[st:mid], arr[mid:en]을.. 2022. 2. 19.
삽입정렬(Insertion Sort) 개념/시간복잡도/Stable/In-place 삽입정렬에 대한 이해 - 삽입정렬이란, 새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 알고리즘이다. - 새로운 원소를 올바른 위치에 삽입시켜나가는 과정을 모든 원소에 대해 수행하면 정렬이 완성된다. N = 8인 다음과 같은 수열을 오름차순으로 정렬해보자. 0번째 인덱스에 있는 수는 그 자체로 정렬이 되어있으므로 그 다음 인덱스인 1번 인덱스 부터 올바른 위치에 삽입을 시작한다. 인덱스 1번 이전에 있는 수와 1번을 비교했을 때, 인덱스 0번에 있는 수 3은 인덱스 1번에 있는 수 7보다 작으므로 자리 교환없이 삽입을 끝낸다. 이후, 인덱스 2번에 있는 수를 이전까지 정렬된 수열 [3, 7] 에 삽입한다. 인덱스 2번 이전에 있는 수들과 2번을 비교했을 때, 인덱스 1번에 있는 수 7은 인.. 2022. 2. 11.
버블정렬(Bubble sort) 개념/시간복잡도/Stable/In-place 버블정렬에 대한 이해 - 버블 정렬이란, 인접한 두 원소를 비교해 나가며 가장 큰 원소를 끝으로 보내는 과정을 N-1번 반복하는 알고리즘이다. - 선택정렬과 유사하게, N-1번 부터 1번까지의 자리에 대하여 남아있는 수들 중 가장 큰 수를 각 자리로 보낸다. - 이 때, 버블정렬은 남아있는 수들 중 가장 큰 수를 인접한 두 수를 비교해가며 찾는다. N = 8인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때, 7번째 자리에 위치해야 할 숫자는 인덱스 0번부터 7번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 인접한 두 수를 비교해가며 가장 큰 수를 끝으로 보낸다. 인덱스 0번과 1번에 있는 숫자를 비교하였을 때, 0번에 있는 숫자 3은 1번에 있는 숫자 7보다 작으므로 넘어간다. 이어서, 인덱스 1번에.. 2022. 2. 11.
선택정렬(Selection sort) 개념/시간복잡도/Unstable/In-place 선택정렬에 대한 이해 - 선택 정렬이란, N-1번부터 1번까지의 자리에 대하여 해당 자리에 넣어야 하는 원소를 선택하는 알고리즘이다. - 오름차순으로 정렬한다면, N-1번부터 1번까지의 자리에는 남아있는 수들 중 가장 큰 수를 선택하여 넣어야 한다. N = 8인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때, 7번째 자리에 위치해야 할 숫자는 인덱스 0번부터 7번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 따라서 0번부터 7번까지의 인덱스를 순회하여 가장 큰 숫자가 있는 인덱스 1번을 알아낸다. 이후, 인덱스 7번에 있는 숫자 0과 1번에 있는 숫자 7을 swap() 함수를 이용하여 교환한다. 6번째 자리에 위치해야 할 숫자는 인덱스 0번 부터 6번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 따라.. 2022. 2. 3.

티스토리툴바