정렬

1. 선택정렬

• 정렬되지 않은 리스트의 최솟값을 정렬된 리스트의 마지막에 추가한다 

# 선택 정렬 
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_index = i # 최솟값의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # swap 
    
print(array)

 

2. 삽입 정렬

• 하나의 값씩 정렬된 리스트 내의 적절한 위치에 삽입한다

# 삽입 정렬
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j-1] > array[j]:
            array[j-1], array[j]= array[j], array[j-1] # swap
        else:
            break

print(array)

 

# 삽입 정렬 -2 (while문)
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    j = i
    while array[j-1] > array[j]:
        array[j-1], array[j]= array[j], array[j-1] # swap
        j -= 1 
        if j < 1:
            break

print(array)

 

3. 퀵 정렬

• pivot 값보다 작으면 오른쪽, 크면 왼쪽에 두고 각 오른쪽 부분과 왼쪽 부분을 다시 정렬한다 

# 퀵 정렬 
array = [7,5,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
    if start >= end: # start == end, 원소가 1개인 경우 
        return 
    
    pivot = start 
    left = start + 1 
    right = end 
    
    while left <= right:
        # left부터 시작해서 pivot 값보다 큰 값이 나올 때까지 
        while left <= end and array[left] <= array[pivot]:
            left += 1 
        # right부터 시작해서 pivot 값보다 작은 값이 나올 때까지 
        while right > start and array[right] >= array[pivot]:
            right -= 1 
        
        if left > right: # 엇갈리면 right, pivot 교체 
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
            
    # 분할 이후 왼쪽 부분, 오른쪽 부분 각각 정렬
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

 

# 퀵 정렬 -2
array = [7,5,9,0,3,1,6,2,4,8]

def quick_sort(array):
    # 길이기 1인 경우 
    if len(array) <= 1:
        return array 
    
    pivot = array[0] # 첫 번째 원소
    tail = array[1:] # 그 외 
    
    left_side = [x for x in tail if x <= pivot] # pivot보다 작거나 같은 숫자들
    right_side = [x for x in tail if x > pivot] # pivot보다 큰 숫자들 
    
    # 분할 이후 왼쪽, 오른쪽 각각을 정렬하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 

4. 계수 정렬

• 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능

• 중복된 데이터가 많을수록 유리함 

• 빈도수 테이블을 만들고 이에 따라 새로운 정렬된 리스트를 만들어냄 

# 계수 정렬
array = [7,5,9,0,3,1,6,2,4,8]

# 모든 범위를 포함하는 리스트 (빈도 저장) 
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]] += 1 
    
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

 

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬