11_기본정렬

1. 정렬(sort)

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 프로그램 개발시 빈번하게 정렬을 필요로 함
• 다양한 알고리즘이 고안되었으며 알고리즘 학습의 필수사항

2. 버블 정렬(bubble sort)

• 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면(작으면) 자리를 바꾸는 정렬 알고리즘

https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif

 

def bubblesort(data):
    for i in range(len(data) -1):
        swap = False
        for j in range(len(data) - i -1):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                swap = True
        if swap == False:
            break

    return data

data_list = [80, 90, 100, 70, 50]
bubblesort(data_list)

[50, 70, 80, 90, 100]

 

3. 삽입 정렬(insertion sort)

• 인덱스(key) 앞에 있는 데이터(A)부터 비교해서 key가 더 작으면(크면) 데이터(A)값을 뒤 인덱스로 복사
• key가 더 큰 데이터를 만날 때까지 반복
• 큰 데이터를 만난 위치 바로 뒤에 key를 이동

https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif

 

def insertion_sort(data):
    for i in range(len(data) -1):
        for j in range(i+1, 0, -1):
            if data[j - 1] > data[j]:
                data[j - 1], data[j] = data[j], data[j - 1]
            else:
                break
    return data

data_list = [ 80, 90, 100, 70, 50]
insertion_sort(data_list)

[50, 70, 80, 90, 100]

 

4. 선택 정렬(selection sort)

• 주어진 데이터 중, 최소값을 찾음
• 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
• 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif

 

def selection_sort(data):
    for i in range(len(data) -1):
        min = i
        for j in range(i + 1, len(data)):
            if data[min] > data[j]:
                min = j
        data[min], data[i] = data[i], data[min]
    return data

data_list = [ 80, 90, 100, 70, 50]
selection_sort(data_list)

[50, 70, 80, 90, 100]