[이코테] 4. 정렬 알고리즘

 

 

 

* 선택정렬

- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다 * n

 

 

 

 

result = []
def selection_sort1(data):
    if len(data) > 1:
        n = data[0]
        m = data[1:]
        temp = min(m)
        index = 0
        if n > min(m):
            index = m.index(temp)
            m[index] = n
            result.append(temp)
        else:
            result.append(n)
        return selection_sort1(m)
    else:
        result.append(data[0])
        
def selection_sort2(array):
    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]
    print(array)
    
    
data_list = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
selection_sort1(data_list)
print(result)
selection_sort2(data_list)

 

 

 

 

 

 

* 삽입정렬

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

- 선택 정렬보다 효율적

 

 

 

 

* study 하면서 피드백받은 건데 insertion_sort1로 쓴 코드는 버블정렬이라고 한다..!

 

def insertion_sort1(data):
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] > data[j]:
                # temp = data[j]
                # data[j] = data[i]
                # data[i] = temp
                data[i], data[j] = data[j], data[i]
    print(data)
        
def insertion_sort2(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break
    print(array)
    
    
data_list = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
insertion_sort1(data_list)
data_list = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
insertion_sort2(data_list)

 

 

 

 

 

* 퀵정렬

 

 

 

 

 

 

 

 

def quick_sort1(data, start, end):
    if (start >= end): return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and data[left] <= data[pivot]:
            left += 1
        while right > start and data[right] >= data[pivot]:
            right -= 1
        if left > right:
            data[right], data[pivot] = data[pivot], data[right]
        else:
            data[left], data[right] = data[right], data[left]
    quick_sort1(data, start, right - 1)
    quick_sort1(data, right + 1, end)


def quick_sort2(data):
    if len(data) > 1:
        pivot = data[0]
        tail = data[1:]
        left = [x for x in tail if x <= pivot]
        right = [x for x in tail if x > pivot]
        
        return quick_sort2(left) + [pivot] + quick_sort2(right)
    else:
        return data
    
data_list = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
quick_sort1(data_list, 0, len(data_list) - 1)
print(data_list)
data_list = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(quick_sort2(data_list))