[Algorithms] Sorting정렬 한꺼번에 살펴보기

이 글은 필자가 학교 강의(이상호 교수님의 "자료구조")를 듣고 복습차 정리한 글입니다. 참고해주세요!

 

정렬: 물건을 크기 순으로 오름차순/내림차순으로 나열하는 것

※ 정렬 알고리즘을 통해 파악해야 할 사실은 알고리즘의 특성도 중요하지만 각 알고리즘의 진행 방식에 따른 복잡도, 어떤 상황에서 사용하면 가장 효과적인지를 면밀하게 생각해보는 것이 가장 중요하다고 판단됩니다.

 

정렬 알고리즘은 6가지 이상이 있지만, 대표적인 6가지로 추려서 보면, 단순하지만 비효율적인 방법(삽입 정렬, 선택 정렬, 버블 정렬)과 복잡하지만 효율적인 방법(퀵정렬, 힙 정렬, 병합 정렬)로 나뉩니다. (배열을 이용한 정렬 구현으로)하나씩 살펴보도록 하겠습니다.

 

삽입 정렬Insertion Sort    코드확인

앞부터 정렬을 순서대로 하되, 정렬된 앞 부분에 새로운 값을 올바른 자리에 삽입하는 방식으로 이루어집니다.

이렇게 배열을 블록으로 생각해본다면 정렬이 안된 리스트의 가장 첫번째 값을 정렬이 된 곳으로 순서대로 정렬하는 방식으로 이루어집니다.

평균 시간 복잡도는 O(N^2)로 하나씩 뽑아서 넣는 방식으로 진행되겠지만, 만약 정렬이 된 리스트에서 이를 시행한다면 O(N)까지 줄어들을 수 있습니다. 즉 O(N^2)~O(N)

 

 

 

 

선택 정렬Selection Sort  코드확인

삽입 정렬과 동일하게 앞부터 정렬을 순서대로 하되(최솟값으로 정렬이 순서대로 된 리스트), 정렬이 안된 리스트에서는 최솟값을 보내서 정렬이 된 리스트의 끝에 붙는 형식으로 진행됩니다. ( 즉, 최솟값을 선택해서 앞으로 보내버리기)

리스트의 원소 개수 만큼 최솟값을 확인하고 넘겨주는 작업으로 시간 복잡도는 O(N^2)번으로 작동됩니다. 즉 O(N^2)

 

 

 

버블 정렬Bubble Sort 코드확인

버블정렬은 인접한 2개의 리스트를 비교하여 순서대로 되어있도록 정렬하는 방식으로 진행됩니다.

from GeeksforGeeks

인접한 두 수를 비교하여 큰 수를 뒤로 보내버리면 최댓값이 제일 큰 수로 정렬되는 효과를 볼 수 있습니다.

인접한 두수를 비교하는 방식을 매 리스트마다 계속해야 하므로 O(N^2)의 시간 복잡도를 가지게 됩니다.

 

 

퀵 정렬Quick Sort 코드확인 / 병합 정렬Merge Sort 코드확인

퀵 정렬과 병합정렬은 대표적인 분할-정복 기법(Divide and Conquer)으로, 분할하여 분할된 영역이내에서 정복하는 기법으로 작용됩니다. 퀵정렬과 병합정렬은 비슷한 기법으로 이용되어서 묶게 되었습니다.

 

퀵 정렬Quick Sort

옆에 나온 그림을 참고하여 보면, 축값인 Pivot(첫번째 그림의 네모로, 임의로 배열의 첫번째 값을 pivot을 정하였다. 배열의 중간이나, 끝값, 등 아무 값이나 pivot으로 정할 수 있으나 고르는 것마다 성능이 달라질 수 있다.)을 중심으로 하나의 리스트를 pivot보다 큰 값과 작은 값으로 나눈다. 이렇게 나뉜 배열들을 중심으로 퀵 정렬을 따로 실행하게 된다.

중심으로 나눠 log2N, 각각의 원소 N마다 실행되므로 O(N*log2N)을 가진다.

 

 

요약해보면,

1. pivot 잡기 2. pivot 중심으로 큰 값/작은 값 배열 나누기 3. pivot을 큰 값, 작은 값 배열 중심에 설정(크기대로) 이를 반복하는 설정을 드러낸다.

from Wikipedia

 

병합 정렬Merge Sort

병합 정렬은 퀵 정렬보다 더 간단합니다.  병합 정렬은 리스트를 2로 나뉘어서 나뉜 리스트 사이에서 각각 정렬하여(log2N) 합병하면서 다시 정렬(N)하는 방식으로 진행됩니다. 즉, 시간 복잡도는 O(N*log2N)입니다.

from 교수님 자료

 

 

힙 정렬Heap Sort 코드확인

힙 정렬은 트리 구조 관련된 정렬이라 다음 포스팅에 다뤄보도록 하겠습니다.