정렬 알고리즘 정리

버블 정렬이란?

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 인덱스를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
선택 정렬과 기본 개념이 유사하다.

 

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

위 과정이 마치 거품이 차오르는 것처럼 정렬이 된다고 하여 버블정렬이라고 한다.

 

코드 예제

import sys

b = [1, 9, 3 ,30,21,23,100,3,45,2,10,32,4,19,13]

def swap(b,i,j):
    temp=b[i]
    b[i]=b[j]
    b[j]=temp

def bubbleSort(b):
    for i in range(1,len(b)):
        for j in range(1,len(b)+1-i):
            if(b[j-1]>b[j]):
                swap(b,j-1,j)
                
    return b

a=bubbleSort(b)
for i in a:
    print(i)

 

n번 비교,n-1번 비교 ... 1번 비교 -> n(n-1)/2만큼의 시간이 걸림 

즉, O(n^2)의 시간 복잡도를 가짐

 

선택정렬이란?

최솟값을 계속 선택해서 처음 최솟값은 1번째 다음 2번째 이런 형식으로 정렬하는 알고리즘

 

코드 예제

def sellectionSort(b):
    for i in range(0,len(b)-1):
        min=i
        for j in range(i+1,len(b)):
            if(b[j]<b[min]):
                min = j
            swap(b,i,min)
    return b
a=sellectionSort(b)
for i in a:
    print(i)

 

삽입정렬이란?

앞의 배열이 모두 정렬되어있다고 가정하고 뒤에 배열의 원소를 앞의 배열과 비교해나가는 정렬 알고리즘

당연히 그냥 정렬할때는 앞의 하나의 인덱스만 정렬되어있다고 가정하고 뒤의 원소부터 선택 후 정렬

 

코드예제

def insertionSort(b):
    for i in range(1,len(b)):
        CurrentElement = b[i]
        j=i-1
        while(j>=0 and b[j]>CurrentElement):
            b[j+1]=b[j]
            j=j-1
        b[j+1]=CurrentElement
    return b

a=insertionSort(b)
for i in a:
    print(i)

 

해당 알고리즘 들은 모두 O(n^2)의 시간 복잡도를 가져 효율적이지 못하다고 볼 수 있다.

다음 글에는 합병정렬 퀵정렬 등 실제 라이브러리에서 제공하는 정렬에서도 쓰이는