データ構造-ソート・セット

3487 ワード
アルゴリズム#アルゴリズム# データ構造 名学習 ツールバーの テキストリンク
ソート・タイプ
  • 挿入ソート
  • 選択ソート
  • 泡配列(Buble sort)
  • ユニットソート(ユニットソート)
  • 連結ソート(連結ソート)
  • ヒップホップソート、キュー(heap sort,queue)
  • クイックソート、(クイックソート)
  • 基数ソート
  • カウントソート(カウントソート)
    • 1.ソートの挿入

  • コンセプト
    手にしたカードを整理する方式を切り口とし、あるカードを整理する際に、特定のカードを順番に並べたカードと比較して、特定のカードの位置を特定する.

  • コード#コード#
    • void insertSort(int arr[], int n) {
	int key, i, j;
	for (i = 1; i < n; i++) {//index 1 부터 모두 확인
		key = arr[i];
		for (j = i - 1; j >= 0 && key < arr[j]; j--) { // key의 값보다 크면 인덱스를 +1 이동
			arr[j + 1] = arr[j];
		}// 아니라면 그 위치가 key가 있어야할 위치
		arr[j + 1] = key; //외부에서 j를 정의했기 때문에 for문 밖에서도 사용가능
	}
}

  • 時間の複雑さ
    O(n^2)

  • くうかんふくざつさ
    O(n)

  • 特長
    アレイが小さいほど効率が向上
    • 2.ソート選択(select sort)

  • コンセプト
    配列の最上位値を探し、順番に並べ替えます.

  • コード#コード#
    • void selectSort(int arr[], int n) {
	int indexMin, temp; // 최솟값 인덱스
	for (int i = 0; i < n - 1; i++) {
		indexMin = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[indexMin] > arr[j]) {
				indexMin = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[indexMin];
		arr[indexMin] = temp;
	}
}

  • 時間の複雑さ
    O(n^2)

  • くうかんふくざつさ
    O(n)
    • 3.バブルソート(Buble sort)

  • コンセプト
    隣接する2つのインデックス(j,j+1)を比較し,順次並べ替えた.

  • コード#コード#
    • void bubbleSort(int arr[], int n) {
	int temp;
	for (int i = 0; i < n; i++) {//회수
		for (int j = 0; j < n - 1-i;j++) { 
			if (arr[j] > arr[j + 1]) {// 인접한 인덱스 비교
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

  • 時間の複雑さ
    O(n^2)

  • くうかんふくざつさ
    O(n)

  • 特長
    配列が整うほど効率が上がる
    • 4.セルのソート
  • コンセプト
    挿入ソート(insert sort)の補完は、挿入ソートに対して隣接するindex+1しか移動できず、移動する位置が遠くなるほどコスト(write)の問題を解決する方法は
    • である.
    void shellSort(int arr[], int n) {
	int i, k, j, gap, value;
	for (gap = n / 2; gap > 0; gap /= 2) {
		if (gap % 2 == 0) {
			gap++;
		}
		for (i = 0; i < gap; i++) { // gap으로 나눈 기준까지
			for (j = i + gap; j < n; j += gap) { //인덱스 정렬 시작
				value = arr[j]; // 기준이 되는 인덱스 이자, 변경할 값 
				for (k = j - gap; k >= i && arr[k] > value; k -= gap) {//기준이 되는 j의 인덱스 아래로 정렬진행
					arr[k + gap] = arr[k]; //  값들을 순차대로 정렬
				}
				arr[k + gap] = value; // 맨 마지막 값을 업데이트 해줌!!
			}
		}
	}
}

  • へいきんじかんふくざつさ
    O(n^1.5)

  • くうかんふくざつさ
    O(n)

  • 特長
    交換が必要な値が遠く離れている場合は、挿入ソートよりもコストがかかります.
    • 5.連結ソート(連結ソート)
    void merge(int arr[], int first, int mid, int last) {
	int i, j, k, l;
	i = first;
	j = mid + 1;
	k = first;
	while (i <= mid && j <= last) {
		if (arr[i] > arr[j]) {
			sort[k++] = arr[j++];
		}
		else {
			sort[k++] = arr[i++];
		}

	}
	if (i > mid) {// i쪽만 값을 넣었을때 j의 값을 모두 넣는다.
		for (l = j; l <= last; l++) {
			sort[k++] = arr[l];
		}
	}
	else {
		for (l = i; l <= mid; l++) {
			sort[k++] = arr[l];
		}
	}
	for (l = first; l <= last; l++) {
		arr[l] = sort[l];
	}
}

void mergeSort(int arr[], int first, int last) {
	int mid;
	if (first < last) {
		mid = (first + last) / 2;
		mergeSort(arr, first, mid);
		mergeSort(arr, mid + 1, last);
		merge(arr, first, mid, last);
	}
}
    6.お尻の位置合わせ、キュー(heap sort、queue)
    7.クイックソート、(クイックソート)
    8.基数ソート
    9.カウントソート
    NCサーバによるリアルタイムサーバログの遠隔サーバへの送信
    AngualRJSディレクティブにおけるアウトバウンド属性表現の活性化