버블정렬, 삽입정렬, 선택정렬

버블정렬 (Bubble Sort)

• 인접한 데이터를 비교하며 자리를 바꾸는 방식
• 시간복잡도: $O(n^2)$
  
  
  

연산횟수는 $\sum_{i=1}^{k}{n} = \frac{n(n-1)}{2}$
따라서 시간복잡도는 $O(n^2)$

의사코드(pseudo-code)

BubbleSort(arr[]){
  arr[SIZE]
  for i = 1 to SIZE -1 {
      for j = 0 to SIZE - i {
          if(arr[j]> arr[j+1]){
              swap(arr[j], arr[j+1])
          }
      }
  }
}

삽입정렬 (Insertion Sort)

• 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식
• 시간복잡도: $O(n^2)$

의사코드(pseudo-code)

InsertionSort(arr[]){
  arr[SIZE]
  for i = 1 to SIZE -1 {
      for j = i to SIZE 0 (j--) {
          if(arr[j] < arr[j - 1])
              swap(arr[j], arr[j-1])
          }
      }
  }
}

선택정렬 (Selection Sort)

• 최소, 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식
• 시간복잡도: $O(n^2)$

의사코드(pseudo-code)

SelectionSort(arr[]){
  arr[SIZE]
  for i = 0 to SIZE - 1 {
      min = i
      for j = i + 1 to SIZE {
          if(arr[j] < arr[min]){
              min = j
          }
          swap (arr[i], arr[min])
      }
  }
}