알고리즘(정렬)

정렬

데이터를 순서대로 재배열 하는 것

가장 기본적이고 중요한 알고리즘

비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있다.

오름차순과 내림차순 사전식 정렬 등이 있다.

레코드 : 정렬시켜야 될 대상

여려 개의 필드로 이루어짐

정렬 키: 정렬의 기준이 되는 필드

정렬이란 레코드들을 키의 순서로 재배열 하는 것

[번호][이름][키][나이] => 레코드

   EX) 나이를 기준으로 정렬한다고하면 나이가 정렬 키가 됨
   

선택정렬 : 기준에 맞는 값을 선택하여 정렬하는 방법

def selection_sort(A):
    n=len(A)
    for i in range(n-1):
        least = i;
        for j in range(i+1,n):
            if(A[j]<A[least]):
                least = j
        A[i],A[least] = A[least], A[i]
        print(A,i+1);
A = [9,8,7,6,5,4,3,2,1]
selection_sort(A)

결과:
[1, 8, 7, 6, 5, 4, 3, 2, 9] 1
[1, 2, 7, 6, 5, 4, 3, 8, 9] 2
[1, 2, 3, 6, 5, 4, 7, 8, 9] 3
[1, 2, 3, 4, 5, 6, 7, 8, 9] 4
[1, 2, 3, 4, 5, 6, 7, 8, 9] 5
[1, 2, 3, 4, 5, 6, 7, 8, 9] 6
[1, 2, 3, 4, 5, 6, 7, 8, 9] 7
[1, 2, 3, 4, 5, 6, 7, 8, 9] 8

선택 정렬의 시간복잡도는
(n-1)+(n-2)+(n-3)....+1=n(n-1)/2= O(n²)

삽입정렬 : 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 방법

def insertion_sort(A):
    n = len(A)
    for i in range(1,n): // 2번째 부터 비교
        key = A[i] //key는 새로 들어갈 대상
        j = i-1 // j는 새로 들어갈 대상 바로 앞의 값 j+1은 현재 값 j+1 = i = key
        while j >=0 and A[j] >key: //j가 0보다 작지 않고 새로 들어갈 대상이 바로 앞의 값보다 작을 경우까지 반복
                                   // 즉 비교할 앞의 대상이 있고 앞의 값보다 작을 때까지 반복
            A[j+1] = A[j] // 큰값인 앞의 값을 새로들어갈 대상의 현재 자리값에 넣어주고 
                          // 즉 자리를 바꿔주고
            j-=1 // j=j-1 즉 비교 대상을 앞으로 한칸 이동
        A[j+1] = key //현재 위치에 새로 들어갈 값 최종으로 저장
        print(A,i)
a= [5,3,8,4,9,1,6,2,7]
insertion_sort(a)
결과:
[3, 5, 8, 4, 9, 1, 6, 2, 7] 1
[3, 5, 8, 4, 9, 1, 6, 2, 7] 2
[3, 4, 5, 8, 9, 1, 6, 2, 7] 3
[3, 4, 5, 8, 9, 1, 6, 2, 7] 4
[1, 3, 4, 5, 8, 9, 6, 2, 7] 5
[1, 3, 4, 5, 6, 8, 9, 2, 7] 6
[1, 2, 3, 4, 5, 6, 8, 9, 7] 7
[1, 2, 3, 4, 5, 6, 7, 8, 9] 8

복잡도 분석
최선의 경우: 이미 정렬되어 있는 경우 : 비교: n-1 번만 일어남 O(n)
최악의 경우: 역순으로 정렬되어 있는 경우 모든 단계에서 앞의 놓인 자료를 전부 뒤로 이동 O(n²)
평균의 경유 O(n2)

특징

많은 이동 필요 -> 레코드가 큰 경우 불리하다!
안정된 정렬방법 정확도가 높다!
대부분 정렬되어 있으면 매우 효율적이다!**