정렬 알고리즘

선택정렬 O(N^2)

• 1. 인덱스의 맨 앞부터 시작해서 가장 작은값을 찾는다
• 2. 현재 인덱스와 가장 작은값의 위치를 바꾼다
• 3. 반복

삽입정렬 O(N^2)

• 1. 현재인덱스와 다음인덱스를 비교하고 작으면 위치를 바꾼다
• 2. 위과정을 더이상 작지 않을떄까지 반복한다.

버블정렬 O(N^2)

• 1. 현재인덱스와 다음인덱스를 비교후 크면 위치를 바꾼다(큰수를 앞으로 보냄)
• 2. 이를 계속 반복한다(선택정렬의 역버전)

합병정렬O(nlogN)

• 1. 모든 인덱스를 분할한다
• 2. 인덱스를 비교 정렬하며 합치는 것을 반복한다

 

 

퀵 정렬 평균 O(NlogN) 최악(정렬되어있을경우) O(N^2)

• 1. 피봇값을 정하고 그 값을 중심으로 작은값은 왼쪽 큰값은 오른쪽에 배열한다.
• 2. 왼쪽과 오른쪽에 각각 다시 피봇값을 정하고 그 값을 중심으로 작은값은 왼쪽 큰값은 오른쪽에 배열한다
• 3. 정렬될때까지 반복하고 마지막에 합친다.