[Algorithm #정리] Python의 sorting 알고리즘 및 예제 코드
정렬(Sorting) 데이터를 특정 기준에 따라 순서대로 나열하는 것. 정렬 알고리즘 selection sort (선택정렬) 가장 작은것 탐색 ⇒ 자리 변경 ⇒ 반복 시간복잡도 N-1만큼 작은것 탐색, {N*(N+1)}/2 ⇒ O(N^2) insertion sort (삽입 정렬) 하나씩 ⇒ 적절한 위치에 삽입 무조건 자리를 바꾸는 선택정렬과의 차이 ⇒ 삽입정렬은 필요시에만 자리 변경 발생 시간복잡도 반복문 2번 사용 O(N^2), 단 최선(완벽하게 정렬된)의 경우 O(N) quick sort (퀵 정렬) 기준이 되는 요소(pivot)지정, 한쪽 끝 ⇒ 한쪽은 pivot보다 작은것, 다른쪽은 pivot보다 큰 것⇒ 큰 것 ↔ 작은 것 자리 교환 ⇒ 반복 ⇒ 큰 것 탐색과 작은 것 탐색 간 교차 발생 시 ⇒ 작은 것 ↔ pivot 간 자리 교환(분할, partition 발생) → 파티션 기준 데이터 분할 발생 ⇒ pivot 다시 선정 ⇒ 반복 ⇒ 분할된 리스트의 요소가 1이거나 비는 경우 ⇒ 종료 시간복잡도 평균 O(NlogN) 단, 최악의 경우 O(N^2). 데이터가 이미 정렬되어 있는 경우다. <code1> array = [ 5 , 7 , 9 , 0 , 3 , 1 , 6 , 2 , 4 , 8 ] def quick_sort ( array , start , end ): if start >= end : return pivot = start print ( 'pivot element is ' , pivot , end = ':' ) left = start + 1 right = end while left <= right : while left <= end and array [ left ] <= array [ pivot ]: ...