Ch 10-1単純ソートアルゴリズム

序曲
資料構造でソートについて話すのは,探索を説明するためである.
データ構造の三大演算
(1)挿入(2)削除(3)ナビゲーション
このとき,探索の性能は避けられないテーマである.
従って,探索前に行わなければならないソートは,資料構造と密接に区別できないアルゴリズムである.
10−1から簡単な並べ替えアルゴリズムを学び,10−2から比較的複雑な並べ替えアルゴリズムを学習した.
複雑なソートアルゴリズムはもちろん性能が比較的よいが,簡単なソートアルゴリズムは実現に優れている.(必要に応じて、実装のために関数の一部に数行書くことができます.)
つまり、目的を達成するためには、その時に書きやすいので、簡単なソートアルゴリズムも知っておく必要があります.
(1)泡並べ替えアルゴリズム
1.アルゴリズムの例
4 2 3 1があると仮定します.
この4つのうち最大の1つが最後に送信されます.
その過程は以下の通りである.
4 2 3 1と4と2を比較して、より大きいものを後ろに->2 4 1
2 4 3 1は4と3より大きく後ろへ->2 3 1
同じ過程を経ると、2 3 1 4になります.
最後の4つの過程を除いて
2 3 1 4->2 3 1 4->2 1 3 4.
21を用いて最後のプロセスを行う.
2 1 3 4->1 2 3 4.
その利点は、大量のデータをソートするのに適していないが、実現しやすいことです.
2.実施

#include <stdio.h>//버블 정렬

void BubbleSort(int array[], int n)//n은 데이터의 개수
{
	int i, j;
	int temp;
	for (i = 0; i < n - 1; i++)//총 n - 1회 실시,처음에는 array[n - 2],array[n - 1]이 마지막 비교
	{
		for (j = 0; j < (n - i) - 1; j++)//처음에는 arrya[n - 1]과 array[n - 2]까지 그다음부터 1씩 줄어서 마지막에는 array[0]와 array[1]비교만 하고 끝
        //횟수로 생각해도 편하다. 처음에 n - 1회 그다음부터 1회씩 줄어듬, 마지막에는 1회
		{
			if (array[j] > array[j + 1])
			{
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
}//똑같다 ㅎㅎ

int main()
{
	int i, T;
	int array[100];
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &array[i]);
	}
	BubbleSort(array, T);
	for (i = 0; i < T; i++)
	{
		printf("%d\n", array[i]);
	}
	return 0;
}

3.性能
ソート・パフォーマンス評価の2つの基準
1.比較回数
2.移動回数
比較演算の無条件はn(n−1)/2,すなわち時間複雑度はO(n^2)である.
wast caseでは,比較回数と移動回数が一致した.
(2)ソート選択
データ量が少ない場合、ソートを選択するとパフォーマンスに有利になります.
しかし、実際には、これは泡のソートとあまり性能の違いはありません.
1.アルゴリズムの例
ex.
1 2 4 3と番号付けされた配列から最大値1を選択し、新しいメモリ領域に格納します.
残りの2.43の最高値2を保存...
すなわち,新しい配列には1 2 3 4が格納される.
その欠点は、追加のメモリ容量が必要であることです.
2.改良モデル
最初のセルとして1 4 2 3の最大値を選択->1 4 2 3
4 2 3の最高値は2番目のセル、1 2 4 3/2番目のセルの2に送信され、既存の2番目のセルのデータは2番目のセルの2に送信されます.
4つの3の最大値を3番目のセルに移動->1 2 3 4
つまり、総重量はn-1回でよい.(n番目は必須X)
これにより、余分なメモリ容量が不要になります.
3.実施
https://www.acmicpc.net/problem/2750
選択ソートを使用してこの問題を解決するコード

#include <stdio.h>//선택 정렬

void SelSort(int array[], int n)
{
	int i, j;
	int min;
	int min_index;
	int temp;
	for (i = 0; i < n - 1; i++)
	{
		min = 1001;
		for (j = i; j < n; j++)
		{
			if (min > array[j])
			{
				min = array[j];
				min_index = j;
			}
		}
		temp = array[i];
		array[i] = min;
		array[min_index] = temp;
	}
}

int main()
{
	int i, T;
	int array[1000];
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &array[i]);
	}
	SelSort(array, T);
	for (i = 0; i < T; i++)
	{
		printf("%d\n", array[i]);
	}
	return 0;
}

授業で学んだことを実装し、解決します.

#include <stdio.h>//선택 정렬

void SelSort(int array[], int n)
{
	int i, j;
	int min_idx;
	int temp;
	for (i = 0; i < n - 1; i++)
	{
		min_idx = i;//처음에는 array[i]와 비교
		for (j = i; j < n; j++)
		{
			if (array[min_idx] > array[j])
			{
				min_idx = j;//array[i]보다 작은 값이 있으면 그 칸을 min_idx라 한다.
			}
		}
		temp = array[i];
		array[i] = array[min_idx];
		array[min_idx] = temp;//array[i]와 비교한 칸들 중 가장 작은 값이 저장된 칸 swap
	}
}

int main()
{
	int i, T;
	int array[1000];
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &array[i]);
	}
	SelSort(array, T);
	for (i = 0; i < T; i++)
	{
		printf("%d\n", array[i]);
	}
	return 0;
}

4.性能評価
まず、どれが一番高いかを比較しなければなりません.
比較演算はn(n+1)/2,すなわち時間複雑度はO(n^2)である.
しかしバブルソートとは異なり、移動していないため、バブルソートよりも性能が良い.
(3)位置合わせを挿入
1.アルゴリズム

ひとつ(?)すべて
5があると仮定すると、5より小さい数と5より大きい数の間に5が挿入される.
5より大きい数値が表示されたら、前のセルを挿入します.
これらを繰り返します.
では、選択ソートとの違いを見てみましょう.
選択ソートは、一番前の値を選択することによって向上します.
位置合わせを挿入するには、位置合わせされていないセルの数値を入力して、位置合わせされたセルの適切な位置に挿入します.

ソートを挿入する難点-挿入後、後ろのソートを右に1つにします.

挿入する必要があるデータはtempとして格納されます.
挿入する位置のセルから挿入するデータの元の位置まで、セルを右に押してtempルールを挿入する位置に保存します.
2.実施
https://www.acmicpc.net/problem/2750
ソートを挿入してこの問題を解決するコード

#include <stdio.h>//삽입 정렬

void InsertSort(int array[], int n)
{
	int i, j, k;
	int temp;
	for (i = 1; i < n; i++)
	{
		temp = array[i];
		for (j = 0; j < i; j++)
		{
			if (temp < array[j])
			{
				for (k = i - 1; k >= j; k--)
				{
					array[k + 1] = array[k];
				}
				array[j] = temp;
				break;
			}
		}
	}
}

int main()
{
	int i, T;
	int array[1000] = { 0 };
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &array[i]);
	}
	InsertSort(array, T);
	for (i = 0; i < T; i++)
	{
		printf("%d\n", array[i]);
	}
	return 0;
}

講義

#include <stdio.h>//삽입 정렬

void InsertSort(int array[], int n)
{
	int i, j, k;
	int temp;
	for (i = 1; i < n; i++)
	{
		temp = array[i];
		for (j = i - 1; j >= 0; j--)
		{
			if(array[j] > temp) array[j + 1] = array[j];
            else break;
		}
        array[j + 1] = temp;
	}
}

int main()
{
	int i, T;
	int array[1000] = { 0 };
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &array[i]);
	}
	InsertSort(array, T);
	for (i = 0; i < T; i++)
	{
		printf("%d\n", array[i]);
	}
	return 0;
}

私との決定的な違いは、比較演算と移動を同時に行うことです.
図のように.

3.性能評価
比較演算は最悪の場合n(n−1)/2(Bubbleソートや選択ソートなど)であるため,時間的複雑度はO(n^2)である.
最適な場合、最適なBubbleソート、選択ソート、挿入ソートのパフォーマンスが最適(演算回数はnに比例)
最悪の場合、Bubbleソートのように比較演算に従って移動する必要があるため、パフォーマンスはソートを選択するよりも劣る.