[백엔드TIL] 정렬 알고리즘을 알아본다.

버블 정렬 (Bubble Sort)
인접한 두 원소를 비교하며 큰 값을 뒤로 이동시키는 방식으로 정렬합니다.
전체 데이터를 순회하며 가장 큰 값이 맨 뒤에 위치하게 됩니다.
시간 복잡도는 최악 및 평균 경우에 O(n^2)이며, 간단하지만 비효율적인 정렬 알고리즘입니다.
삽입 정렬 (Insertion Sort)
배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 원소를 정렬된 부분에 삽입합니다.
삽입 정렬은 거의 정렬된 배열에 대해서는 효율적이며, 최선의 경우 시간 복잡도는 O(n)입니다. 하지만 최악 및 평균 경우에는 O(n^2)입니다.
선택 정렬 (Selection Sort)
주어진 배열에서 가장 작은 값을 선택하여 배열의 처음부터 차례대로 위치시키는 방식으로 정렬합니다.
시간 복잡도는 항상 O(n^2)이며, 버블 정렬과 유사한 성능을 가집니다.
퀵 정렬 (Quick Sort)
분할 정복(divide and conquer) 기법을 사용하여 배열을 분할하고 각 부분을 재귀적으로 정렬합니다.
평균적으로 매우 효율적인 알고리즘으로, 시간 복잡도는 평균적으로 O(n log n)입니다. 하지만 최악의 경우에는 O(n^2)이 될 수 있습니다.
병합 정렬 (Merge Sort)
분할 정복 기법을 사용하여 배열을 반으로 나눈 뒤, 각 부분을 정렬하면서 병합하는 방식으로 정렬합니다.
항상 O(n log n)의 시간 복잡도를 가지며, 안정적인 정렬 알고리즘 중 하나입니다.
힙 정렬 (Heap Sort)
최대 힙(또는 최소 힙) 자료구조를 사용하여 정렬하는 방식입니다.
시간 복잡도는 항상 O(n log n)이며, 대량의 데이터를 정렬하는 데 유용합니다.

 

- 버블 정렬 

거품 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)

 

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.

3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.

 

 

 

즉, 그림으로 보면 다음과 같은 과정을 거친다.

 

 

 

 

이 때, 각 라운드를 진행 할 때마다 뒤에서부터 한 개씩 정렬되기 때문에, 라운드가 진행 될 때마다 한 번씩 줄면서 비교하게 된다.

한마디로 정리하자면 이렇다.

총 라운드는 배열 크기 - 1 번 진행되고,

각 라운드별 비교 횟수는 배열 크기 - 라운드 횟수 만큼 비교한다.

 

 

*삽입 정렬을 이해해보자

->어떤 대상을 '오름차순'으로 정렬할 때 삽입 정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고, n번째 원소까지 이 방식을 반복함으로써 정렬을 진행할 수 있다. 예를 들어 [6, 2, 3, 4, 1]이라는 배열을 삽입 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다.

초기 배열 상태. Array[CurIndex]는 임시 변수에 저장하여 값을 기억해둔다.

 현재 선택된 원소의 앞 원소와 비교를 하며 현재 원소의 적절한 위치를 찾는 방식이기 때문에, 우선 Array[0]와 Array[CurIndex]를 비교를 하게 된다. 이때, Array[0] > Array[CurIndex]이므로 0번째 인덱스의 원소를 뒤로 미뤄버린다.

현재 대상 원소인 Array[CurIndex]의 값보다 Array[0]의 값이 크기 때문에, 해당 값을 다음 인덱스인 1로 미뤄버린다.

그렇다면 다음과 같은 상태가 되어 있을 것이다.

 이때 가장 앞 원소까지 탐색이 종료되었으므로, 최종적으로 미뤄졌던 인덱스에 현재 인덱스의 값을 '삽입'한다.

0번째 인덱스에서 미뤄지는 것이 종료되었으므로, 해당 위치에 초기에 선택했던 값을 삽입한다.

그렇다면 다음과 같은 상태가 되어 있을 것이다.

 2번째 원소에 대한 탐색이 종료되었으므로, 이번에는 3번째 원소에 대한 값을 기준으로 위 과정을 똑같이 반복해준다. 즉 초기 상태는 아래와 같아질 것이다.

초기 배열 상태. 마찬가지로 Array[CurIndex]의 값은 임시 변수에 저장하여 값을 기억해둔다.

 마찬가지로 현재 원소의 앞의 원소만을 탐색하기 때문에, Array[1]과 Array[CurIndex]의 값을 비교하게 될 것이다. 이때, Array[1] > Array[CurIndex]이므로 해당 원소의 위치를 뒤로 미뤄버린다.

해당 원소를 뒤로 미뤄버린다.

따라서 다음과 같은 상태가 되어 있을 것이다.

 다음으로 Array[0]와 Array[CurIndex]를 비교해보면 Array[CurIndex]의 값이 더 크기 때문에, 탐색을 종료한다. 탐색을 종료한 지점이 1이므로, 해당 위치에 임시로 저장해두었던 Array[CurIndex]의 값을 삽입해준다.

Array[0] < Array[CurIndex]이므로, 1번째 원소에서 탐색이 종료되고 해당위치에 기억해두었던 값을 삽입해주면된다.

 이러한 과정을 n번째 원소까지 반복해준다면 정렬이 완료된다.