정렬 알고리즘

1. 선택 정렬O(n^2)

• 앞쪽부터 최소값을 찾아 위치를 변경. 비교횟수는 많지만 교환 횟수가 적음
• 구현이 간단하나 효율이 좋지않음
• 시간복작도 best,worst,avg 동일
  

2. 버블 정렬O(n^2)

• 앞쪽부터 인접한 원소와 비교하며 맨 끝부터 정렬. 즉 가장 큰값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬
• 구현이 간단하나 효율이 좋지않음
• worst,average,best 모두 동일
  

3. 삽입 정렬O(n^2)

• 앞쪽부터 i개만큼씩 정렬해 나감
• 버블 정렬의 비효율성을 개선하기 위해 등장. 버블 정렬의 비교 및 교환 횟수를 줄임으로써 효율이 좋음. 입력 배열이 정렬되어 있을수록 속도가 빠름. 즉 역순이면 성능이 좋지 않음
• worst,average 동일, best 이미 정렬되어 있다면 O(n)
• ex : 10 1 3 5
  • 10 비교 -> 10 1 3 5
  • 10,1 비교 -> 1 10 3 5
  • 1,10과 3 비교 -> 1 3 10
  • 1,3,10과 5비교 -> 1 3 5 10

4. 병합 정렬O(n logN)

• 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 방식
• 항상 일정한 시간 복잡도를 가지며, 안정적이며 좋은 성능을 낸다. 쪼갠 배열을 저장할 공간이 필요하므로 추가적인 메모리가 필요. 큰 데이터에 적합.
• worst,average,best 모두 동일
  

5. 퀵 정렬O(N^2)
하나의 축(pivot)을 정해서 이 축보다 작은 값은 왼쪽에 큰값은 오른쪽에 위치시킨다. 이를 반복
일반적으로 가장 준수한 효율을 보이지만 최악의 경우에는 훨씬 많은 시간이 소요되므로 안정성이 좋지 않다는 특징이 있다. (ex pivot이 최소,최대 값에 잡히면 worst) 축을 어떻게 설정하느냐에 따라 성능 차이가 심함. 하지만 쉽게 발생하지 않고 일반적으로 병합정렬보다 20%이상 빠름

• avg,best 동일, worst는 n^2

• 1. pivot point 지정
• 2. 분할에 앞서, 비교를 진행하기 위해 가장 왼쪽,오른쪽 변수 생성
• 3. right부터 비교. right가 left보다 클 때만 반복하며, pivot보다 크면 right를 하나 감소시키고 비교를 반복. pivot보다 작은값을 찾으면 반복을 중지
• 4. left 를 비교. right가 left보다 클 때만 반복하며, 비교한 값이 pivot보다 작으면 left를 하나 증가시키고 비교를 반복. pivot보다 큰 배열 값을 찾으면, 반복을 중지
• 5. left 인덱스의 값과 right 인덱스의 값을 바꿔준다.
• 6. 3,4,5 과정을 left < right가 만족 할 때 까지 반복
• 7. 위 과정이 끝나면 left의 값과 pivot을 바굼
• 8. 맨 왼쪽부터 left -1까지, left+1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복

이미지 출처 : https://jbhs7014.tistory.com/180