버블정렬, 선택정렬, 삽입정렬, 퀵정렬 코드

파이썬으로 작성하는 정렬

파이썬 정렬에 대해 코드로 정리하였습니다. 바로 컴파일해도 정상 작동합니다

python sort.py

2.5 kB

datas=[21, 3, 1, 5, 4, 0, 9]

# 버블정렬
# 시간 복잡도 O(n^2)로 매우 느리다.
# n번 사이클 돌며 n-1번 비교
# 뒤 인덱스부터 정렬 된다.
def bubbleSort(x):
    length = len(x)-1
    swap = False
    for i in range(length):
        swap = False
        for j in range(length-i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
                swap = True
        if swap == False:  # 스왑이 없으면 정렬이 끝난것이므로 더이상 루프를 돌지 않게 한다.
            break            
    return x
#print(bubbleSort(datas))

# 선택정렬
# 1.주어진 데이터 중에 최소값을 찾음 2.최소값을 맨 앞 자리로 교체 3.시작 인덱스+1 로 반복
# 앞 인덱스부터 정렬 된다.
# n!*n번 반복 O(n^2)
# 버블정렬보다 빠르다.
def selectionSort(x):
    for i in range(len(x)-1):
        indexMin = i
        for j in range(i+1, len(x)):
            if x[indexMin] > x[j]:
                indexMin = j
        x[i], x[indexMin] = x[indexMin], x[i]
    return x
#print(selectionSort(datas))

# 삽입정렬
# 두번째 인덱스부터 시작, 왼쪽 데이터와 비교하여 더 작으면 그 인덱스로 삽입
# k번째 반복 후의 결과 데이터는, 앞쪽 k + 1 항목이 정렬된 상태
# (n-1)*(n-1)번 반복 O(n^2)
# 선택정렬, 버블정렬보다 빠르다.
def insert_sort(x):
    for i in range(len(x)-1):
        for j in range(i+1, 0, -1):
            if x[j] < x[j-1]:
                x[j], x[j-1] = x[j-1], x[j]
            else:
                break
    return x
#print(insert_sort(datas))

# 퀵정렬
# 1. 기준(pivot)을 정해서 작은것 left 큰것 right로 모으는 함수를 작성 2. 재귀로 반복 3. 왼쪽 + 기준점 + 오른쪽 리턴
# 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장
# 임시로 캐시를 만들어서 정렬하므로 메모리 차지가 크지만 속도가 빠르다.
# n log n + n 번 O(n log n)
def quicksort(x):
    if len(x) <= 1:
        return x
    pivot = x[len(x) // 2]    # 중앙값을 찾음
    left, right, equal = [], [], []        # 임시 캐시
    for i in x:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
        else:
            equal.append(i)
    return quicksort(left) + equal + quicksort(right)
#print(quicksort(datas))