정렬 알고리즘 구현해보기

선택 정렬

배열에서 최솟값을 찾는다.

최솟값이 배열의 맨 앞 원소보다 작으면 자리를 교체한다.

맨 앞의 원소를 제외하고 반복한다.

 

mylist = [199, 22, 33, 12, 32, 64, 72, 222, 233]

def 선택정렬(mylist):
    min_index = 0 # 최소 인덱스 기본을 0으로
    count = 0 # 몇번 반복했는지
    
    for _ in range(len(mylist)): # 배열 길이 만큼 반복
        for i in range(count, len(mylist)): # count부터 시작(1번 반복했으면 배열 0번째는 젤 작은 수이니 빼고 시작)
            if mylist[i] < mylist[min_index]: # 배열의 최솟값 인덱스 찾기
                min_index = i
        mylist[count], mylist[min_index] = mylist[min_index], mylist[count] # 위치 바꾸기
        count += 1 # 반복했으니까 1 더하기
        min_index = count # 최솟값 인덱스를 기본 맨 앞으로
        
    return mylist
    
선택정렬(mylist) # [12, 22, 32, 33, 64, 72, 199, 222, 233]

 

 

삽입 정렬

정렬 범위를 1칸씩 확장해간다.

새롭게 들어온 값을 기존 값의 뒤에서부터 비교해서 자리를 교체한다.

 

mylist = [199, 22, 33, 12, 32, 64, 72, 222, 233]

def 삽입정렬(mylist):
    extend_range = 2 # 정렬 범위 두개부터 시작

    for _ in range(len(mylist) - 1): # 정렬 범위 두개부터 배열의 길이-1 까지 반복
        for j in range(extend_range - 1, 0, -1): # 정렬 범위의 맨 뒤부터 비교하기
            if mylist[j] < mylist[j-1]:
                mylist[j], mylist[j-1] = mylist[j-1], mylist[j]
        extend_range += 1 # 정렬 범위 늘리기

    return mylist

print(삽입정렬(mylist)) # [12, 22, 32, 33, 64, 72, 199, 222, 233]

 

 

병합 정렬

주어진 배열을 원소가 하나만 남을 때 까지 계속 쪼갠다. (분할)

크기순으로 정렬하면서 조금씩 합친다. (정복)

원래 크기의 배열이 될 때 까지 반복.

 

mylist = [199, 22, 33, 12, 32, 64, 72, 222, 233]

def 병합정렬(mylist):
    
    if len(mylist)< 2: # 길이가 1이면 그대로 반환
        return mylist
    
    half = len(mylist) // 2 # 배열의 길이 절반
    first_group = 병합정렬(mylist[:half]) # 두개로 나누는 것 중 앞 배열 그룹
    second_group = 병합정렬(mylist[half:]) # 두개로 나누는 것 중 뒷 배열 그룹
    merged_list = [] # 크기 비교해서 넣을 배열

    while first_group and second_group: # 앞 배열과 뒷 배열에 원소가 있으면
        if first_group[0] < second_group[0]: # 비교해서 더 작은거 넣기
            merged_list.append(first_group.pop(0))
        else:
            merged_list.append(second_group.pop(0))
    while first_group: # 배열의 길이가 둘이 안같은 경우
        merged_list.append(first_group.pop(0)) # 앞에서부터 꺼내서 넣음(작은것)
    while second_group:
        merged_list.append(second_group.pop(0))
    
    return merged_list # 크기 비교해서 넣은 배열 다시 반환해서 그룹으로 들어감

병합정렬(mylist)

 

 

퀵정렬

피봇이라는 기준 값을 설정 (보통 앞, 중간, 뒷 값을 기준으로 함)

피봇을 기준으로 왼쪽에 작은 값, 오른쪽에 큰 값 그룹으로 나눔.

왼쪽 오른쪽 그룹에서 이를 반복.

 

mylist = [199, 22, 33, 12, 32, 64, 72, 222, 233]

def 퀵정렬(mylist):

    if len(mylist) < 2:
        return mylist # 길이가 1이면 그대로 반환
        
    first_group = [] # 작은것을 왼쪽에 둘 리스트
    second_group = [] # 큰것을 오른쪽에 둘 리스트
    pivot = mylist[0] # 가장 첫번째 요소를 피봇값으로 정했다

    for value in mylist[1:]: # 피봇값인 첫째 요소를 제외하고 반복
        if value < pivot:
            first_group.append(value) # 더 작으면 왼쪽에
        else:
            second_group.append(value) # 더 크면 오른쪽에
    
    return 퀵정렬(first_group) + [pivot] + 퀵정렬(second_group) # 왼쪽 오른쪽 리스트에서도 동일하게 재귀 함수 호출
    
퀵정렬(mylist) # [12, 22, 32, 33, 64, 72, 199, 222, 233]