ソートの練習

C++ アルゴリズム（初級）

直接選択法

int main() {
	int n;
	cin >> n;
	int *arr = new int[n];
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
	}
        //ここから本題
	for(int i = 0; i < n; i++) {
		int min = MyArray::ArrayMinIndex(arr, i, n);
		swap(arr[min], arr[i]);
	}
	for(int i = 0; i < n; i++) {
		cout << arr[i] << endl;
	}
	delete[] arr;
}

バブルソート

int main() {
	int n;
	cin >> n;
	int *arr = new int[n];
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for(int j = 0; j < n-1; j++) { //n-1回繰り返す。
		for(int i = n-1; i > j; i--) { //配列は[0, n-1]の範囲内
			//前の配列の数のほうが大きいならソート
			if(arr[i-1] > arr[i]) {
				swap(arr[i-1], arr[i]);
			}
		}
	}
	for(int i = 0; i < n; i++) {
		cout << arr[i] << endl;
	}
}

シェーカーソート

	int left, right, shift;
	left = 0; right = n-1;

	while(left < right) {
		//左から右
		for(int i = left; i < right; i++) {
			if(arr[i] > arr[i+1]) {
				swap(arr[i], arr[i+1]);
				shift = i; //ここまで、ソートした
			}
		}
		right = shift;
		for(int i = right; i > left; i--) {
			if(arr[i] < arr[i-1]) {
				swap(arr[i], arr[i-1]);
				shift = i;  //ここまでソートした。
			}
		}
		left =shift;
	}

	for(int i = 0; i < n; i++) {
		cout << arr[i] << endl;
	}

}

arr[7] = {2, 5, 6, 9, 3, 7, 8}なら、

→               |
{2, 5, 6, 3, 7, 8, 9} shift = 6; right = 6;

   |           ←
{2, 3, 5, 6, 7, 8, 9}  break;     shift = 2; left = 2; 

       →     |
{2, 3, 5, 6, 7, 8, 9} shift = 2(変化しない) right = 2;
ここで終了。


レコード型（structとか、classとか)のソートは、
ポインタをコピーして、ポインタ上でやり取りする。

const int N = 4;
typedef struct _girl {
	char* name;
	int age;
} girl;

int main() {
	girl samp[] = {
		{"Ann", 18},
		{"Rolla", 19},
		{"Nancy", 16},
		{"Eluza", 17},
	};
	girl *p[N];
	for(int i = 0; i < N; i++) {
		p[i] = &samp[i]; //ポインタを作る
	}
	for(int i = 0; i < N-1; i++) {
		char* min = p[i]->name;
		int s = i; //ポインタ
		//最小の文字を選ぶ
		for(int j = i + 1; j < N; j++) {
			if(strcmp(p[j]->name, min) < 0) {
				min = p[j]->name;
				s = j;
			}
		}
		swap(p[i], p[s]);
	}
	for(int i = 0; i < N; i++) {
		cout << p[i]->name << p[i]->age << endl;
	}

}
ここでは単純選択法でソートした。

数字のときは普通の不等号でいいが、
文字のときはint strcmp( const char *文字列1, const char *文字列2 );
を使う。

返り値	説明
0未満	str1はstr2よりも小さい
0	str1とstr2は同一
0より大きい	str1はstr2よりも大きい


基本挿入法

int main() {
	int n;
	cin >> n;
	int *arr = new int[n];
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for(int i = 1; i < n; i++) {
		for(int j = i -1; j >= 0; j--) {
			//左側のほうが大きい
			if(arr[j] > arr[j+1]) {
				swap(arr[j], arr[j+1]);
			} else {
				break;
			}
		}
	}
	for(int i = 0; i < n; i++) {
		cout << arr[i] << endl;
	}
}

arr[6] = {80, 50, 56, 30, 51, 71}のとき

i = 1 j= [0,0]
80 50
50 80

i = 2 j = [1,0]
50 80 56
50 56 80      break;

i = 3 j = [2,0]
50 56 80 30
50 56 30 80
50 30 56 80
30 50 56 80


基本挿入法を応用して、シェルソート

int main() {
  int n;
  cin >> n;
  int *arr = new int[n];
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  int gap = n/2;   //部分数列を作る。
  while(gap > 0) {
    for(int k = 0; k < gap; k++) {            //k = 0 only gap == 1
      //青色のforが基本挿入法と同じ働きをしている。
      for(int i = k+gap; i < n; i = i + gap) { //for(int i = 1; i < n; i++)
      	for(int j = i-gap; j >= k; j = j-gap) {    //for(int j = i-1; j >= 0; j--)
          if(a[j] > a[j+gap]) {  //if(a[j] > a[j+1])
	    swap(a[j], a[j+gap]);   //swap(a[j], a[j+1]);
	  } else {
            break;
          }
	}
      }
    }
    gap /= 2;  //とびとびを減らしてみる。
  } //end while

  for(int i = 0; i < n; i++) {
    cout << arr[i] << endl;
  }
}