정렬 - (2) 삽입, 퀵 정렬

https://www.youtube.com/watch?v=oyzWDtMquo4

 

삽입 정렬

• 자료 배열의 모든 요소를 앞에서 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입
• 안정 정렬
• 제자리 정렬
• Best case : O(N)
• Worst case :  O(N^2)  , 1+ 2 + 3 + ... (N-1) 번의 비교가 필요, 데이터 상태에 따라 선응 편차가 큼

퀵 정렬

• 임의의 숫자를 기준으로 좌축에는 작은 값을 우측에는 큰 값을 두어 정렬
• 불안정 정렬
• 속도 빠름( 참조 지역성이 높고 교환이 불필요한 요소를 거의 교환X → 교환 획수가 적음)
• Worst case : O(N^2) 
• 재귀를 사용하지 않으면 구현이 복잡함

hi 에서는 4보다 작은 요소를 , lo에서는 4보다 큰 요소를 찾고 교체합니다.

만약 hi, lo의 위치가 겹치면 기준값과 자리를 바꿔주면 , 기준값을 기준으로 좌측은 기준보다 작은 값 그리고 우측은 기준보다 큰 값이 정렬 되고 이를 반복