[제주코딩베이스캠프] 눈떠보니 코딩테스트 전날 | 정렬이론

* 정렬 알고리즘 *

1. 선택정렬
2. 삽입정렬
3. 병합정렬
4. 퀵정렬

---

1. 선택정렬

가장 작은 값을 골라 정렬 앞쪽에 두는 것을 반복하는 정렬이다.

입력값=[5,10,66,77,54,32,11,15] 정렬된리스트=[] while 입력값: 정렬된리스트.append(min(입력값)) 입력값.pop(입력값.index(min(입력값))) print(정렬된리스트) #최솟값 구하는 함수 만들기 def 최솟값(array): 최소=array[0] cnt=0 for i in array: if 최소>i: 최소=i index=cnt cnt+=1 print(최소) print=("최솟값의 idx",index)

 

---

2. 삽입정렬

앞에서부터 차례대로 넣는데, 넣을 때 이 값보다 크게 되면 뒤에 놓고
이 값보다 작게 되면 앞에 놓는 정렬이다.

입력값=[5,10,66,77,54,32,11,15] 정렬된리스트=[] def 삽입값이들어갈인덱스(정렬된리스트,삽입값): for i in range(len(정렬된리스트)): if 삽입값<정렬된리스트[i]: return i return len(정렬된리스트) while 입력값: 삽입값=입력값.pop(0) 인덱스= 삽입값이들어갈인덱스(정렬된리스트,삽입값) 정렬된리스트.insert(인덱스,삽입값)

---

3. 병합정렬

: 리스트를 각각 모두 나눈 뒤 하나씩 합쳐나가는 정렬

# O(nlogn) > 병합정렬이 시간복잡도가 가장 좋다 # 재귀함수 사용 입력값 = [5, 10, 66, 77, 54, 32, 11, 15] 정렬된리스트 = [] 전체인덱스 = 7 중간값 = 7 // 2 # 3 입력값[:중간값 + 1] 입력값[중간값 + 1:] def 병합정렬(입력리스트): # 분할 파트 입력리스트의길이 = len(입력리스트) 결과값=[] if 입력리스트의길이 <= 1: return 입력리스트 중간값 = 입력리스트의길이 // 2 그룹_하나 = 병합정렬(입력리스트[:중간값]) 그룹_둘 = 병합정렬(입력리스트[중간값:]) # 정복 파트 while 그룹_하나 and 그룹_둘: if 그룹_하나[0] < 그룹_둘[0]: 결과값.append(그룹_하나.pop(0)) else: 결과값.append(그룹_둘.pop(0)) while 그룹_하나: 결과값.append(그룹_하나.pop(0)) while 그룹_둘: 결과값.append(그룹_둘.pop(0)) return 결과값 print(병합정렬(입력값))

---

4. 퀵정렬

# O(nlogn) > 퀵정렬 (best) # 0(n**2) > 퀵정렬 (worst) # 피봇 pivot 입력값 = [66, 77, 54, 32, 10, 5, 11, 15] def 퀵정렬(입력리스트): 입력리스트의길이 = len(입력리스트) if 입력리스트의길이 <= 1: return 입력리스트 피벗값 = 입력리스트.pop(0) 그룹하나 = [] 그룹둘 = [] for i in range(입력리스트의길이 - 1): if 입력리스트[i] < 피벗값: 그룹하나.append(입력리스트[i]) else: 그룹둘.append(입력리스트[i]) return 퀵정렬(그룹하나) + [피벗값] + 퀵정렬(그룹둘) print(퀵정렬(입력값))