よくある問題/ソート - C/C++の宿題を片付けます@wiki

ソート

---

バブルソート（基本交換法、隣接交換法）

安定な内部ソート。O(n^2)

C

#include<stdio.h>
int main(){
  int i, j, temp, ptr[] = {8,4,3,7,6,5,2,1}, n = 8;

  /* Bubble sort */
  for(i = 1; i <= n-1; ++i)
    for(j = 0; j < n-i; ++j)
      if(ptr[j] > ptr[j+1]){
        temp = ptr[j];
        ptr[j] = ptr[j+1];
        ptr[j+1] = temp;
      }

  for(i = 0; i < n; ++i) printf("%d ", ptr[i]);
  return 0;
}

---

挿入ソート（インサーションソート、基本挿入法）

安定な内部ソート。O(n^2)

C

#include<stdio.h>
int main(){
  int i, j, temp, ptr[] = {8,4,3,7,6,5,2,1}, n = 8;

  /* Insertion sort */
  for(i=1; i<n; ++i)
    for(j=i; j>0 && ptr[j-1]>ptr[j]; --j){
        temp = ptr[j];
        ptr[j] = ptr[j-1];
        ptr[j-1] = temp;
    }

  for(i = 0; i < n; ++i) printf("%d ", ptr[i]);
  return 0;
}

---

選択ソート（セレクションソート）

内部ソートだが、安定ソートではない。O(n^2)

C

#include<stdio.h>
int main(){
  int i, j, min, temp, ptr[] = {8,4,3,7,6,5,2,1}, n = 8;

  /* Selection sort */
  for(i = 0; i < n-1; ++i){
    min = i;
    for(j = i+1; j<n; ++j)
      if(ptr[min] > ptr[j]) min = j;
    temp = ptr[i];
    ptr[i] = ptr[min];
    ptr[min] = temp;
  }

  for(i = 0; i < n; ++i) printf("%d ", ptr[i]);
  return 0;
}

---

マージソート

安定ソートだが、O(n)の外部記憶を必要とする。O(n log n)

C

#include<stdio.h>
int temp[8];
void MergeSort(int *ptr, int l, int r){
  int i, j, k, m;
  if(l >= r) return;
  m = (l+r) / 2;
  MergeSort(ptr, l, m);
  MergeSort(ptr, m+1, r);
  for(i = l; i <= m; i++) temp[i] = ptr[i];
  for(i = m+1, j = r; i <= r; ++i, --j) temp[i] = ptr[j];
  i = l;
  j = r;
  for(k = l; k <= r; k++){
    if(temp[i] <= temp[j]) ptr[k] = temp[i++];
    else ptr[k] = temp[j--];
  }
}
int main(){
  int i, ptr[] = {8,4,3,7,6,5,2,1}, n = 8;

  MergeSort(ptr, 0, n-1);

  for(i = 0; i < n; ++i) printf("%d ", ptr[i]);
  return 0;
}

---