정렬 알고리즘

버블정렬

: 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

 

과정

1. 첫번째 요소와 두번째 요소를, 두번째 요소와 세번째 요소를, ... , 마지막-1 요소와 마지막 요소를 비교하며 교환한다.

2. 1회전을 수행하고 나면 맨 끝에 가장 큰 요소가 가게되므로 맨 끝은 제외하고 정렬을 다시 반복한다.

 

선택정렬

: 제자리 정렬 알고리즘 중 하나이다.

 

과정

1. 주어진 리스트 중에 최소값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다(패스)

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 

삽입정렬

: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 요소들이 이미 어느정도 정렬되어있는 경우 매우 효율적일 수 있다.

 

퀵정렬

:분할 정복 알고리즘 중 하나로 매우 빠른 수행 속도를 자랑한다.

 

과정

1. 리스트 안에 있는 한 요소(피벗)을 선택한다.

2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗 왼쪽으로 이동되고 피벗보다 큰 요소들은 피벗의 오른쪽으로 이동된다.

3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 재 정렬한다.

4. 부분 리스트들이 더이상 분할이 불가능할 때 까지 반복한다.

 

시간복잡도 비교