정렬1

1.Bubble Sort

거품 정렬은 가장 쉬운 정렬이지만 속도가 느리다는 단점이 있습니다.

그래서 비교적 적은 크기의 데이터에 대해서 사용을 하는 경우가 많습니다.

다음과 같은 특징을 가지고 있습니다.

최고 속도 - O(n)

평균 속도 - O(n^2)

최악 속도 - O(n^2)

메모리 사용 - 1

안정성 - 안정

특징 - 작은 코드 크기 (가장 단순 할 듯)

 알고리즘

의사코드 (Pseudocode) 

 

procedure bubbleSort( A : list of sortable items )
  repeat     
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i+1] > A[i] then
        swap( A[i+1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

2. Insert Sort

삽입 정렬은 거품 정렬과 함께 간단한 정렬 중 대표적인 정렬입니다.

안정 정렬이고, 제자리 (in-place) 정렬 이라는 특징도 가지고 있습니다.

제자리 정렬이라 추가적인 메모리는 없어도 되지만, 배열이 길 경우 효율이 떨어진다는 단점도 있습니다.

특징을 정리하면 다음과 같습니다.

최고 속도 - O(n)

평균 속도 - O(n^2)

최악 속도 - O(n^2)

메모리 사용 - 1

안정성 - 안정

특징 - 작은 크기, 제자리 정렬

알고리즘 

의사코드 (Pseudo code)

 for i ← 1 to i ← length(A)-1
   {
     // A[ i ] is added in the sorted sequence A[0, .. i-1]
     // save A[i] to make a hole at index iHole
     item ← A[i]
     iHole ← i
     // keep moving the hole to next smaller index until A[iHole - 1] is <= item
     while iHole > 0 and A[iHole - 1] > item
       {
         // move hole to next smaller index
         A[iHole] ← A[iHole - 1]
         iHole ← iHole - 1
       }
     // put item in the hole
     A[iHole] ← item
   } 

3. Selection Sort

선택 정렬은 내부 정렬 알고리즘의 대표적인 정렬 방법입니다.

최소값을 저장하기 위한 변수 하나만 필요해서 추가적인 공간은 딱 1의 크기만 있으면 됩니다.
도서관에서 책이 꽂혀 있을 때 순서대로 맞추는 경우 저도 모르게 선택 정렬 방법을 사용했던 기억이 납니다.

특징은 다음과 같습니다.

최고 속도 - O(n^2)

평균 속도 - O(n^2)

최악 속도 - O(n^2)

메모리 사용 - 1

안정성 - 불안정

특징 - 내부 정렬 알고리즘

알고리즘

의사코드 (Pseudo code)

for  i <- 1 to i <- length (A) - 1)

   min = i

   for j <- i + 1 to j <- length(A) 

       if A(j) < A(min)

          min = j

       swap A(i), A(min)