정렬

정렬은 주어진 데이터를 일정하게 재배열하는 것이다. 

데이터를 재배열하는 정렬 종류는 다양하다

 

 

1) 버블 정렬

비교해서 큰 데이터를 오른쪽으로 보내서 재배열하는 방법

전체 배열를 모두 조회해서 데이터를 비교한다. -> 반복 : 큰데이터에는 효율적이지 못한 알고리즘이다.

2) 선택 정렬

가장 작은 최솟값을 골라서 맨앞에 보내는 식으로 재배열한다. 

가장 작은 최솟값 고르려면 전체 배열을 모두 조회해야한다. -> 반복 : 마찬가지로 큰데이터에는 효율적이지 못한 알고리즘

 

이처럼 정렬 알고리즘의 성능을 평가하는데에는 주로 '시간복잡도' 개념이 쓰인다. 

시간복잡도란 알고리즘 수행시간이 입력한 값에 따라 얼마나 증가하는지를 나타내는 지표이다. 

출처 : https://junghyun100.github.io/Time-Complexity/

출처: https://wikidocs.net/34790

 

 

 

3) 힙정렬

힙 - 더미, 데이터를 특정한 형태로 쌓아올리는 것을 의미. 

노드간의 관계를 나타내는 이진트리구조에서 힙 구조가 나타난다. 

기본 리스트를 힙정렬로 만들려면 일단 최대 혹은 최소값을 가지는 루트를 설정하고 

루트를 기준으로 값(노드)를 정렬한다. 

 

 

4) 삽입정렬

삽입정렬은 버블정렬과 비슷해보이지만 

모든 데이터를 조회하며 비교하는 버블정렬과 달리

이미 정렬된 부분과 정렬되지 않은 부분을 유지하며

정렬된 부분에는 요소를 삽입하여 배열하므로 버블 정렬보다 효율적인 정렬이다.

 

5) 퀵 정렬

기준을 세워 분할한다(보통 중간값을 기준으로 함).작은 요소는 왼쪽, 큰 요소는 오른쪽에 위치한다.

분할하고 배열하고를 재귀적으로 반복 후 합쳐서 정렬.

 

6)병합 정렬

리스트를 반으로 나눈다. 리스트 크기가 1이하가 될때까지 반으로 나눈다.

나눈 작은 리스트를 정렬한다. 나눴던 리스트의 가장 작은 요소를 비교해서 

작은 순서대로 병합한다. 

입력크기와 상관없이 일정한 시간복잡도를 가진다.