정렬 알고리즘

알고리즘과 자료구조에 대해 다시 짚어보면서

개념을 정리하고 기록해보려고합니다.

 

우선, 오늘 정리할 개념은 정렬 알고리즘입니다.

 

전공 과정상 수업시간에도 다뤄졌던 내용이지만, 확실히 정리해두지 않으면

개념에 대한 이해도가 많이 떨어질 것 같아 시작하게되었습니다.

 

 

Do my utmost. 이제 시작입니다!

 

 

 

 

 

버블 정렬(Bubble Sort)

• 인접한 두 개의 원소를 비교하여 정렬하는 알고리즘
• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(1)

 

<<초기상태>>

[4, 2, 5, 1, 3]

첫번째 원소 4와 두번째 원소 2를 비교한 뒤, 2가 더 작으므로 두 원소의 위치를 바꾼다.

[2, 4, 5, 1, 3]

두번째 원소 4와 세번째 원소 5를 비교, 위치 변동X

세번째 원소 5와 네번째 원소 1 비교, 1이 더 작으므로 두 원소 위치 바꾼다.

[2, 4, 1, 5, 3]

네번째 원소 5와 다섯번째 원소 3 비교, 3이 더 작으므로 두 원소 위치 바꾼다.

[2, 4, 1, 3, 5]

1회전 끝!

위와 같은 방식으로 더이상 교환이 일어나지 않을 때까지 반복한다.

 

 

 

 

 

 

 

삽입 정렬(Insertion Sort)

• 정렬된 부분 집합에 새로운 원소를 삽입하는 알고리즘( 두번째 원소부터 시작하여 비교 )
• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(1)

 

<<초기상태>>

[4, 2, 5, 1, 3]

첫번째 원소 4는 이미 정렬된 상태,

두번째 원소 2를 첫번째 원소와 비교, 2가 더 작으므로 4를 오른쪽으로 이동시킨다.

Key값 2를 4의 자리인 첫번째에 기억시킨다.

[2, 4, 5, 1, 3]

1회전 끝!

 

세번째 원소 5와 4를 비교, 5가 더 크므로 그대로.

2회전 끝

 

네번째 원소인 1과 세번째 원소 5를 비교, 1이 더 작으므로 5를 한칸 뒤로 이동,

1과 두번째 원소 4를 비교, 1이 더 작으므로 4를 한칸 뒤로 이동,

1과 첫번째 원소 2를 비교, 1이 더 작으므로 1을 한칸 뒤로 이동

3회전 끝

[1, 2, 4, 5, 3]

 

이런식으로 마지막 원소인 3도 비교해서 한칸씩 앞으로 가게되면

정렬이 끝나게 된다.

 

 

 

 

 

 

 

선택 정렬(Selection Sort)

• 주어진 리스트에서 최소값을 찾아 맨 앞에 위치한 값과 교체하는 알고리즘
• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(1)

 

<<초기상태>>

[4, 3, 5, 1, 2]

가장 작은 1을 찾아 배열의 맨 앞으로 가져온다.

[1, 3, 5 , 4, 2]

나머지 배열에서 가장 작은 값 2를 찾아 두번째 원소로 가져온다.

[1, 2, 5, 4, 3]

나머지 배열에서 가장 작은 3을 세번째 원소로 가져온다.

[1, 2, 3, 4, 5]

이런 식으로 가장 작은 원소를 찾아서 하나씩 교체하며 정렬한다.

 

 

 

 

 

 

 

퀵 정렬(Quick Sort)

• 분할 정복 방법을 통해 리스트를 정렬하는 알고리즘
• pivot값을 기준으로 큰 값과 작은 값으로 나눠 분할하고, 이를 재귀적으로 반복한다.
• 시간 복잡도 : O(nlogn) ~ O(n^2)
• 공간 복잡도 : O(logn) ~ O(n)

 

<<초기상태>>

[5, 2, 6, 8, 4, 9, 1, 3, 7]

pivot : 5일때

pivot을 기준으로 두개의 리스트로 나눔

pivot 보다 작은쪽과 큰쪽으로 나눈다.

2 : 작음, 7 : 큼 -> 교환X

6 : 큼, 3 : 작음 -> 교환

[5, 2, 3, 8, 4, 9, 1, 6, 7]

8 : 큼, 1 : 작음 -> 교환

[5, 2, 3, 1, 4, 9, 8, 6, 7]

4 : 작음, 9 : 큼 -> 교환X

모두 비교한 뒤, pivot을 4와 교환하여 가운데로 옮긴다.

[4, 2, 3, 1, 5, 9, 8, 6, 7]

1회전 끝!

pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 독립적으로 퀵정렬을 진행한다.

리스트의 크기가 0이나 1이 될때까지 반복

 

 

 

 

 

 

 

 

병합 정렬(Merge Sort)

• 분할 정복 방법을 통해 리스트를 정렬하는 알고리즘
• 리스트를 반으로 나눠 각각 정렬한 후, 합병한다.
• 시간 복잡도 : O(nlogn)
• 공간 복잡도 : O(n)

 

<<초기상태>>

[38, 27, 43, 3, 9, 82, 10, 66]

리스트를 두개로 분할한다.

[38, 27, 43, 3]과 [9, 82, 10, 66]

[38, 27] [43, 3] [9, 82] [10, 66]

[38] [27] [43] [3] [9] [82] [10] [66]

[27, 38] [3, 43] [9, 82] [10, 66]

[3, 27, 38, 43] [9, 10, 66, 82]

왼쪽 리스트 맨 앞 원소와 오른쪽 리스트 맨 앞 원소 중 더 작은 값을 가져온다.(반복)

[3, 9, 10, 27, 38, 43, 66, 82] 

 

 

 

 

 

 

퀵 정렬과 병합 정렬은 시간 복잡도가 작아서 일반적으로 많이 사용되지만,

정렬하려는 데이터의 크기나 형태에 따라 다른 알고리즘이 더 적합할 수 있습니다.

 

오늘의 정렬 알고리즘 정리는 여기서 마치도록 하겠습니다.

감사합니다.