알고리즘 (정렬) - 기본적인 정렬 알고리즘(Bubble Sort,Insert Sort)

알고리즘

1. 버블 정렬(Bubble sort)

버블 정렬도 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다.

 

알고리즘 4-2 버블정렬

public int [] bubbleSort(int []A){
    int temp = 0;
    int n = A.length;
    for(int i = 0; i < A.length; i++ ){
        for(int j = 1; j < n; j++){
            if(A[j-1] > A[j] ){
               temp = A[j-1];
               A[j-1] = A[j];
               A[j] = temp;
            }
            if(j == n-1) n--;
        }
    }

    return  A;
}

 

알고리즘은 크게 두 개의 for 루프로 구성이 되어 있다. 첫 번째 for루프, 즉 1️⃣의 for 루픈는 선택 정렬의 for루프와 역할이 똑같다. 루프를 돌 때마다. 제일 큰 원소를 맨 오른쪽으로 보내고 정렬할 배열의 크기를 하나씩 줄인다. 안쪽의 for루프, 2️⃣의 for 루프가 하는 일은 가장 큰 원소를 맨 오른쪽으로 보내는 것이다. 이 부분이 선택 정렬과 다른다. 선택 정렬이 가장 큰 수를 찾은 다음 맨 오른쪽 수와 바꾸는 반면, 버블 정렬은 왼쪽으로 부터 이웃한 수를 비교하면서 순서가 제대로 있지 않으면 하나하나 바꾸어간다. 

 

버블 정렬의 수행 시간을 알아보자. 우선 1️⃣의 for 루프는 선택 정렬에서 처럼  n-1번 순환한다. 2️⃣의 for 루프는 last -1 번 순환한다. last가 n에서 2 까지 1씩 감소하므로 2️⃣의 for루프가 총 순환하는 횟수는 (n-1) + (n-2) + ··· + 2 + 1 = n(n-1)/2이다. 3️⃣은 상수 시간 작업이다. 따라서 버블 정렬의 수행시간은 ϴ(n²)이다.

 

앞에서 소개한 버블 정렬 알고리즘은 알고리즘이 수행을 시작할 때나 중간에 배열이 이미 정령이 되어 있는 상태라도 계속 끝까지 무의미한 순환을 계속한다. 이를 위해 알고리즘에 한가지 장치를 하는 방법이있다.

 

2️⃣의 for 루프가 시작되기 직전에 매번 sorted 표식자를 TRUE로 설정해두고, 이것이 2️⃣for 루프를 도는 동안 변하는지 본다. 중간에 한번이라도 A[i] ↔ A[i+1]의 교환이 일어나면 이것은 FALSE로 바뀐다. 이것이 바꾸지 않았으면 2️⃣의 루프를 도는 동안 한 번도 교환이 일어나지 않았으므로 배열은 이미 정렬되어 있는 상태임을 알 수있다. 이때는 3️⃣에서 return을 함으로써 알고리즘을 끝내 버리면 된다. 이렇게 할 경우 배열이 정렬된 상태로 입력되면 버블 정렬은 1️⃣의 for루프를 첫번째 순환하고 리턴하게 되어 끝난다. 즉, ϴ(n)의 시간이 소용된다.

 

2. 삽입 정렬(Insertion Sort)

처음엔 왼쪽 끝의 숫자(a[0]) 정렬이 끝났다고 간주한다. 계속해서 아직 작업하지 않은 숫자 중에서 왼 쪽 끝에 있는 숫자(a[1])를 꺼내서 왼쪽에 작업이 끝난 숫자(a[0])와 비교한다. 작업이 끝난  숫자(a[1])가 크면 두 개의 숫자 자리를 바꾼다.(이 작업은 작업이 진행 중인 숫자보다 작업이 끝난 숫자가 작을 때까지 반복하거나 작업이 끝나지 않은 숫자가 왼쪽 끝에 도착할 때까지 반복한다.)

 

삽입 정렬은 이미 정렬되어 있는 i개 짜리의 배열에 또 다른 원소를 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한한다. 선택 정렬과 버블 정렬이 n개 짜리 배열에서 시작해서 해당 n의 배열에서 알고리즘 작동영역을 계속 줄여가는 반면 삽입 정렬은 한개 짤리 배열에서 그 크기를 하나씩 늘리는 정렬이다.

 

알고리즘 4-3  삽입정렬

public int [] insertionSort(int[]A){
    for(int i = 1; i <A.length; i++){
    	int lock = i-1;     //📌고정요소 index
        int newItem = A[i]; //✨새 요소
      while(lock >=0 && newItem < A[lock]){ // 1.고정요소와 새요소 비교
      	A[lock+1] = A[lock]; // 2.고정요소가 클 경우 우측 한칸이동
      	lock--;  // 3.다음 고정요소를 부르기 위해 index 왼쪽으로 한칸이동
      }
      A[lock+1] = newItem; // 4.index -1이 될때 index 0자리에 새요소 삽입
    }
    
    return A;
}

 

 

 

1.시나리오(우측으로 이동하는 고정요소가 1개인경우)

1️⃣에서 고정요소의 최 우측 부터 시작해서 새 요소와 비교를한다.  2️⃣새 요소 보다 고정요소가 클 경우 기존의 고정 요소의 자리를 새요소에게 내어 주기 위해  오른쪽으로 한 칸 이동한다. 3️⃣lock이 -1에 다달았을 때 더 방금전 우측우로 한칸 이동한 고정 요소가 index 0이며 최 좌측에 위치한 고정요소 였다는 뜻이다. 4️⃣ index가 -1인 경우는 없으므로 +1을 해서 0으로 만든뒤 index0에 새 요소를 넣어준다.

 

2.시나리오 (우측으로 이동하는 고정요소가 여러개인 경우)

1️⃣고정요소들의 쵝우측 요소A[lock] 부터 시작해서 새요소와  비교한다. 2️⃣새요소 보다 고정요소가 큰 경우 3️⃣ 고정요소는 새 요소에게 자리를 내어주기 위해 오른쪽으로 한칸 이동한다. 4️⃣최 우측에 있는 고정요소 와 새요소와 비요가 끝났으므로 그다음 고정요소를 부르기위해 index를 왼쪽으로 한칸이동시킨다.  다시 1️⃣로 돌아와 A[lock-1]과 새요소를 비교한다. A[lock -1]이 클경우 이전에 고정요소 A[lock]이 위치 했던 자리를 A[lock -1]이 차지하기 위해 A[lock-1]을 오른쪽으로 한칸 이동 시킨다. 3️⃣이때 다음 고정요소 lock - 2와 새 요소를 비교하기 위해 index를 왼쪽으로 한칸 이동시킨다. 다시 1️⃣로 돌아 왔을때 lock이 0보다 작은 -1인 경우 더 이상 새요소와 비교할 고정 요소가 없다는 뜻으로 A배열에 최 좌즉에 도달한 것이다. 이때 4️⃣에 코드가 실행된다 index -1은 존재하지 않고 A[0]이 빈 자리이기 때문에 lock에 +1을해서 A[0]위치에 새요소를 대입하고 해당 새요소와 고정요소 배열의 비교를 끝낸다.

 

 

3.시나리오(우측으로 이동하는 고정요소가 없는 경우)

1️⃣ 고정요소들 중 최 우측에 있는 고정 요소(A[lock])와 새요소를 비교한다. 새요소가 A[lock]보다 클경우 4️⃣ 고정 요소 위치 보다 한 칸 오른쪽이 새 요소의 위치가 된다. 

 

삽입 정렬의 수행시간을 살펴조바  for 루프는 n-1번 순환한다. 매 for 루프에서 1️⃣의 while 루프는 최대 i -1번 순환한다. 가장 운이 나쁘면  A[i]가 A[0]자리에 들어가게 되어 i -1번 순환한다. 가장 운이 좋으면 A[i]가 제자리에 그대로 있게 되어 while 루프는 한 번도 수행되지 않는다. 그러므로 최악의 경우 수행 시간은  1 + 2 + (n -1) = n( n - 1)/2, 즉 ϴ(n²)이다.  보통은 대략 A[1...i -1]에서 평균적으로 절반 정도를 훑고 끝낼 것이다.  그러므로 전체 비교 횟수는 최악의 겨우에 비해  정반 정도 될 것이다. 이 경우에도 여전히 ϴ(n²)이다.

 

삽입 정렬은 O(n²) 시간이 드는 비효율적인 정렬 알고리즘군에 속하지만 배열이 거의 정렬되 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다. 배열이 완전히 정렬된 채로 입력된다면 1️⃣의 while 루프는 한 번도 수행 되지 않으므로 for 루프를 한번 순환할 때 마다 상수 시간이 소요된다. for 루프는 n-1번 순환되므로 ϴ(n)의 시간이든다. 버블 정렬에서는 배열이 이미 정렬되어 있는 경우 무의미한 순환을 하는 낭비를 없애기 위해 특별한 장치를 하는 방법을 설명했다.이 장치로 특수한 경우의 시간을 줄일 수 있지만, 이것을 검사하기 위해 사용한 여분의 코드 때문에 오버헤드가 생긴다. 이에 반해 삽입 정렬은 배열이 이미 정렬된 상태라면 이런 특별한 장치 없이도 효율적으로 끝난다. 이런 매력 때문에 많은 프로그래머들이 다른 정렬을 사용하는 경우에 상화에 따라 가끔 삽입 정렬을 섞어서 쓴다.

 

앞에서 선택 정렬과 버블 정렬이 n개짜리 배열에서 시작하여 그 크기를 하나씩 줄여가는 데 반해, 삽입 정렬은 1개짜리 배열에서 시작하여 그 크기를 하나씩 늘려가는 정렬이라고 하였다. 좀 더 정확히 말하면, 선택 정렬과 버블 정렬이 n개짜리 배열에서 시작하여 아직 정렬되지 않은 배열의 크기를 하나씩 줄이는데 반해여, 삽입 정렬은 1개짜리 배열에서 시작하여 이미 정렬된 배열의 크기를 하나씩 늘리는 정렬이다. 

 

삽입 정렬에는 고등학교 수학의 수학적 귀납법 원리가 그대로 스며들어 있다. 먼저 배열의 크기가 1일 때는 성립한다. (맨 왼쪽 수 하나만으로 이루어져 있으므로 정렬이 되어 있다.) 배열의 크기가 k일 때 성립하면(정렬이되어 있으면)3️⃣의 적정한 삽입으로 크기가 k+1일 때도 성립한다.(정렬이 된다.) 이것으로 삽입 정렬은 올바르게 정렬을 한다는 것이 귀납적으로 증명된 셈이다.  

 

 

[출처 - 쉽게 배우는 알고리즘(개정판),  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7707942187

IT CookBook, 쉽게 배우는 알고리즘(개정판)