[Algorithm] 정렬 - Sorting

정렬 알고리즘

리스트의 값을 오름차순으로 재배치 하는 것으로, 다음과 같다.

unsorted_list = [3, 2, 7, -4, 6]  👉🏻  sorted_list = [-4, 2, 3, 6, 7]

이 때, 정렬 알고리즘은 두 가지 기준에 따라 Stable Sort, in-place Sort로 나뉘어진다.

📌 Stable Sort

Stable 정렬은 중복된 키가 존재하는 배열을 정렬했을 때, 기존 리스트에 있던 순서대로 정렬이 되는 것을 뜻한다.

예를 들어, 다음과 같은 배열이 존재한다고 해보자.

unsorted_list = [3, 6, 2₁, 7, 2₂]

이를 Stable Sort 알고리즘으로 정렬하면 다음과 같은 결과를 얻을 수 있다.

sorted_list = [2₁, 2₂, 3, 6, 7]

Stable Algorithm

• Insertion Sort
• Bubble Sort
• Merge Sort
• Counting Sort

Unstable Algorithm

• Heap Sort
• Selection Sort
• Shell Sort
• Quick Sort

📌 in-place Sort

in-place 정렬은 정렬하는 과정에서 새롭게 사용된 메모리의 양으로 결정된다.

In-place Algorithm

• Insertion Sort
• Selection Sort
• Shell Sort
• Bubble Sort
• Heap Sort
• Quick Sort

Not-in-place Algorithm

• Merge Sort
• Counting Sort
• Radix Sort
• Bucket Sort

--

# 더 보기
선택정렬
버블정렬
삽입정렬
병합정렬
퀵정렬