[알고리즘] 정렬 알고리즘(Sorting Algorithms) 개요

📌 서문

알고리즘 강의에서, 대개 정렬 알고리즘을 가장 먼저 배운다. 정렬 알고리즘은 무엇이고, 왜 공부하는 것이며 강의 초반에 배우는 것일까?

카드놀이를 할 때 정렬을 한 적이 있는데, 컴퓨터는 어떻게 정렬을 수행할까?

 

📌 정의

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order.
컴퓨터 과학에서, 정렬 알고리즘은 하나의 리스트(배열)의 요소들을 일정한 순서에 맞게 분류하는 것을 의미한다.

Sorting algorithm - Wikipedia

 

📌 학습 목적

1. 정렬 알고리즘은 주어진 데이터를 처리하는 알고리즘의 기초가 되는 문제 중 하나이다.

일상에서 주어진 데이터의 집합을 어떠한 규칙으로 나열하는 것(알파벳순, 내림차순, 오름차순 등)을 쉽게 접할 수 있다.

 

2. 다양한 문제 접근 방식을 배우기에 아주 적합하고 주제이다.

정렬 알고리즘에는 아주 다양한 풀이 방식이 있다. 반복문을 활용하거나 자료구조를 활용하거나, 재귀를 활용하는 등 여러 가지 방법의 정렬 알고리즘을 배울 수 있다.

• 버블 정렬(Bubble Sort)
• 삽입 정렬(Insertion Sort)
• 선택 정렬(Selection Sort)
• 쉘 정렬(Shell Sort)
• 퀵 정렬(Quick Sort)
• 합병 정렬(Merge Sort)
• 힙 정렬(Heap)

 

이 외에도 다른 여러 가지 정렬이 있다.

Sorting Algorithms Animations | Toptal®

 

📌 특징

(1) stable / not stable

정렬 알고리즘을 수행한 이후에도 크기가 같은 데이터끼리의 순서가 처음의 입력 순서를 그대로 유지하고 있는가? 그렇다면 stable, 아니면 not stable이다.

크기가 같은 '5' 카드의 순서가 그대로 유지되고 있으면 stable, 그렇지 않으면 not stable이다.

Sorting algorithm - Wikipedia

정렬 알고리즘	stable / NOT stable
버블 정렬	stable
삽입 정렬	stable
선택 정렬	NOT stable
쉘 정렬	NOT stable
퀵 정렬	stable
합병 정렬	stable
힙 정렬	NOT stable

 

2. in-place / not in-place

입력된 데이터를 저장하는 메모리 공간 외에, 상수 크기의 메모리 공간 정도만 필요한가? 아님 추가로 공간이 더 필요한가? 추가로 필요하지 않으면 in-place, 아니면 not in-place이다.

 

여기서 상수는 데이터 크기 n과 무관하다는 뜻이다. 상수는 아래의 표에서 1로 표현하였다.

정렬 알고리즘	Extra Storage Space	in-place / NOT in-place
버블 정렬	1	in-place
삽입 정렬	1	in-place
선택 정렬	1	in-place
쉘 정렬	1	in-place
퀵 정렬	$\log{n}$	NOT in-place
합병 정렬	$n$	NOT in-place
힙 정렬	1	in-place