Algorithmソートのクリア(Sort)
種類
[時間複雑度O(N^2)]
1)泡の位置合わせ(最も効率的)
2)ソート選択
3)挿入ソート(O(N^2)で最も効率的)
[時間複雑度O(N*logN)]
1)クイックソート(ピボットに沿って最悪の場合はO(N^2)
2)連結ソート
3)お尻の位置合わせ(X/常にO(N*logN)を保証する追加メモリが必要で、効率が最も高い)
[時間複雑度O(N)]
1)係数の並べ替え(データの範囲が確定した場合、O(N)の時間的複雑度がある)
:大きさによって数えます!
整列選択(Selection Sort)
ソートを順番に送信し、最小値を選択
1)全てのN個の整数を迂回して最小値を探す(min)
2)この値を先頭のインデックス値とスワップします.
3)1～2回繰り返す
[時間複雑度]-O(N^2)
#include <iostream>
using namespace std;
int main(){
int N = 10, min, arr[10]={10,6,7,5,3,1,4,6,8,9},index;
for(int i=0;i<N-1;i++)
{
min = 9999;
for(int j=i;j<N;j++)
{
if(arr[j] < min){
min = arr[j];
index = j;
}
}
int tmp = arr[i];
arr[i] = arr[index];
arr[index] = tmp;
}
for(auto a : arr){
cout << a << endl;
}
}
バブル整列(Bubble Sort)
隣の値を比較し続け、小さい値を前に送信してソートします.
(1サイクル経過後、最大値は最後)
1)N個の要素を一つずつ前に隣接する要素と比較し、小さい値を前に送信する
2)サイクル1週間後、最大値は後ろにある
[時間複雑度]-O(N^2)
:非効率なソート選択よりも非効率な方法です.
(時間の複雑さは同じですが、実際の実行時間を分析すると、交換のたびに非常に非効率であることがわかります!)#include <iostream>
using namespace std;
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
for(int i=N-1;i>0;i--)
{
for(int j=0;j<i;j++)
{
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for (auto a : arr){
cout << a << endl;
}
}
挿入
位置合わせ値に対する現在の要素の位置合わせを検索して挿入します.
1)アレイの2番目の要素から
2)前の要素と比較して大きくなるまで交換する
3)ループが長ければ長いほど前の要素が整然としている
4)手順1～3を繰り返す
[時間複雑度]-O(N^2)
:O(N^2)時間の複雑さを持つソートで最も効率的
(全て比較する必要がないので)#include <iostream>
using namespace std;
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9},j;
for(int i=1;i<N;i++)
{
j = i;
while(arr[j] < arr[j-1])
{
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
j--;
}
}
for (auto a : arr){
cout << a << endl;
}
}
クイックソート
ピボットを2つのセットに分割してソートします.
[時間複雑度]-O(N*logN)
ピボット位置によって最悪の場合の複雑さはO(N^2)(最大の欠点)
(平均複雑度O(N*logN)
(最悪の場合は=>ソート済み)
(既にソートされている場合は、前述の「ソートの挿入」が有効です!)#include <iostream>
using namespace std;
void quickSort(int* data, int start, int end){
if(start >= end){
return;
}
int key = start; // 피봇 값
int i = start + 1;
int j = end;
int tmp;
while(i <= j){ // i와 j값이 엇갈릴 때 까지 수행
while(data[key] >= data[i]){ // 피봇보다 작은값을 찾을 때 까지
i++;
}
while(data[key] <= data[j] && j > start){ // 피봇보다 큰 값을 찾을 때 까지
j--;
}
if(i <= j){ // 엇갈리지 않았다면 그냥 교환
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}else{ // 엇갈렸다면 key값과 j와 교환
tmp = data[key];
data[key] = data[j];
data[j] = tmp;
}
}
quickSort(data, start, j-1);
quickSort(data,j+1, end);
}
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
quickSort(arr, 0, N-1);
for (auto a : arr){
cout << a << endl;
}
}
連結ソート
まず、ペアリングを続け、ソートをマージします.
(並べ替えられた2つの集合をマージするにはO(N)!
[時間複雑度]-O(N*logN)
#include <iostream>
using namespace std;
int N = 10, sorted[10];
// 두 묶음을 하나로 합치는 과정
void merge(int data[], int m, int middle, int n){
int i=m;
int j=middle+1;
int k=m;
// 두 집합의 값을 비교하며 차례대로 넣는 과정
while(i <= middle && j <= n){
if(data[i] <= data[j]){
sorted[k] = data[i];
i++;
}else{
sorted[k] = data[j];
j++;
}
k++;
}
// 둘 중 남은 한 집합을 마저 더해주는 과정
if(i > middle){
for(int t=j; t<=n; t++){
sorted[k] = data[t];
k++;
}
}else{
for(int t=i; t<=middle; t++){
sorted[k] = data[t];
k++;
}
}
// 정려된 데이터를 실제 배열에 삽입! (실제 배열을 바로 바꾸면 안된다!)
for(int t=m; t<=n; t++){
data[t] = sorted[t];
}
}
void mergeSort(int data[], int m, int n){
// 크기가 1보다 큰 경우
if(m < n){
int middle = (m+n) /2;
/* 일단 둘로 계속 나누는 mergeSort를 진행 */
mergeSort(data, m, middle);
mergeSort(data, middle+1, n);
/* 합치는 과정! */
merge(data, m, middle, n);
}
}
int main(){
int N = 10, array[10]={10,6,7,5,3,1,4,6,8,9};
mergeSort(array, 0, N-1);
for (auto a : array){
cout << a << endl;
}
}
ヒップ位置合わせ(Heap Sort)
「heapツリー構造」(Heap Tree Structure)でソートする方法
[説明]
複数のツリーが存在しますが、値が空ではない「バイナリツリー」と呼ばれます.
濃密な構造を保つ「完全バイナリツリー」を用いた構造は「hipツリー構造」である.
[最大ヒップ]:親ノードが子ノードより大きいヒップ!
[最小ヒップ]:親ノードが子ノードのヒップより小さい!
[臀部生成アルゴリズム]
:hip構造を作成するためのHeapifyアルゴリズムと呼ばれるアルゴリズム
(O(logN)の時間的複雑度-->N/2要素に対して-->O(N*logN)の時間的複雑度)
(上から下へのヒップ構造の作成-->方向の違い!(結果としてヒップ構造が変更される場合があります)
[原理]
1.配列を使用して、整列する要素をバイナリツリーとして表示
2.Hip構造の作成(Heapifyアルゴリズムを使用)
3.ルートと最後の要素の変更
4.2～3回繰り返し、最後に最大値を1つずつ入力
[コード]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
// 최초 최대 Heap 구조로 만들기 위한 Heapify 알고리즘
for(int i=1; i<N ; i++){
int c=i;
do{
int root = (c-1)/2;
if(heap[root] < heap[c]){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
}while(c != 0);
}
// 크기를 줄여가며 반복적으로 heap을 구성!
for(int i=N-1;i>=0;i--){
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
// 다시 최대 heap구조를 만들기 위한 Heapify 알고리즘
int root = 0;
int c = 1;
do{
c = 2*root + 1;
// 자식 중 더 큰 값을 찾기
if(heap[c] < heap[c+1] && c < i-1){
c++;
}
// 루트보다 자식이 더 크다면 교환
if(heap[root] < heap[c] && c < i){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
}while(c < i);
}
for(auto a : heap){
cout << a << ' ';
}
}
ソート数
与えられたデータが大きいときにO(N)時間の複雑さをソートする方法
(必要なメモリはデータの最大容量と同じなので効率が悪い)
[コード]
#include <iostream>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
int count[5];
int array[30] = {
1,3,2,4,3,2,5,3,1,2,
3,4,4,3,5,1,2,3,4,2,
3,1,4,3,5,1,2,1,1,1
};
fill(count, count+5, 0);
for(int i=0;i<30;i++){
count[array[i]-1]++;
}
for(int i=0; i<5; i++){
if(count[i] != 0){
for(int j=0; j<count[i];j++)
{
cout << i+1;
}
}
}
}
Reference
この問題について(Algorithmソートのクリア(Sort)), 我々は、より多くの情報をここで見つけました
https://velog.io/@neity16/Algorithm-정렬Sort-정리
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
ソートを順番に送信し、最小値を選択
1)全てのN個の整数を迂回して最小値を探す(min)
2)この値を先頭のインデックス値とスワップします.
3)1～2回繰り返す
[時間複雑度]-O(N^2)
#include <iostream>
using namespace std;
int main(){
int N = 10, min, arr[10]={10,6,7,5,3,1,4,6,8,9},index;
for(int i=0;i<N-1;i++)
{
min = 9999;
for(int j=i;j<N;j++)
{
if(arr[j] < min){
min = arr[j];
index = j;
}
}
int tmp = arr[i];
arr[i] = arr[index];
arr[index] = tmp;
}
for(auto a : arr){
cout << a << endl;
}
}バブル整列(Bubble Sort)
隣の値を比較し続け、小さい値を前に送信してソートします.
(1サイクル経過後、最大値は最後)
1)N個の要素を一つずつ前に隣接する要素と比較し、小さい値を前に送信する
2)サイクル1週間後、最大値は後ろにある
[時間複雑度]-O(N^2)
:非効率なソート選択よりも非効率な方法です.
(時間の複雑さは同じですが、実際の実行時間を分析すると、交換のたびに非常に非効率であることがわかります!)#include <iostream>
using namespace std;
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
for(int i=N-1;i>0;i--)
{
for(int j=0;j<i;j++)
{
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for (auto a : arr){
cout << a << endl;
}
}
挿入
位置合わせ値に対する現在の要素の位置合わせを検索して挿入します.
1)アレイの2番目の要素から
2)前の要素と比較して大きくなるまで交換する
3)ループが長ければ長いほど前の要素が整然としている
4)手順1～3を繰り返す
[時間複雑度]-O(N^2)
:O(N^2)時間の複雑さを持つソートで最も効率的
(全て比較する必要がないので)#include <iostream>
using namespace std;
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9},j;
for(int i=1;i<N;i++)
{
j = i;
while(arr[j] < arr[j-1])
{
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
j--;
}
}
for (auto a : arr){
cout << a << endl;
}
}
クイックソート
ピボットを2つのセットに分割してソートします.
[時間複雑度]-O(N*logN)
ピボット位置によって最悪の場合の複雑さはO(N^2)(最大の欠点)
(平均複雑度O(N*logN)
(最悪の場合は=>ソート済み)
(既にソートされている場合は、前述の「ソートの挿入」が有効です!)#include <iostream>
using namespace std;
void quickSort(int* data, int start, int end){
if(start >= end){
return;
}
int key = start; // 피봇 값
int i = start + 1;
int j = end;
int tmp;
while(i <= j){ // i와 j값이 엇갈릴 때 까지 수행
while(data[key] >= data[i]){ // 피봇보다 작은값을 찾을 때 까지
i++;
}
while(data[key] <= data[j] && j > start){ // 피봇보다 큰 값을 찾을 때 까지
j--;
}
if(i <= j){ // 엇갈리지 않았다면 그냥 교환
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}else{ // 엇갈렸다면 key값과 j와 교환
tmp = data[key];
data[key] = data[j];
data[j] = tmp;
}
}
quickSort(data, start, j-1);
quickSort(data,j+1, end);
}
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
quickSort(arr, 0, N-1);
for (auto a : arr){
cout << a << endl;
}
}
連結ソート
まず、ペアリングを続け、ソートをマージします.
(並べ替えられた2つの集合をマージするにはO(N)!
[時間複雑度]-O(N*logN)
#include <iostream>
using namespace std;
int N = 10, sorted[10];
// 두 묶음을 하나로 합치는 과정
void merge(int data[], int m, int middle, int n){
int i=m;
int j=middle+1;
int k=m;
// 두 집합의 값을 비교하며 차례대로 넣는 과정
while(i <= middle && j <= n){
if(data[i] <= data[j]){
sorted[k] = data[i];
i++;
}else{
sorted[k] = data[j];
j++;
}
k++;
}
// 둘 중 남은 한 집합을 마저 더해주는 과정
if(i > middle){
for(int t=j; t<=n; t++){
sorted[k] = data[t];
k++;
}
}else{
for(int t=i; t<=middle; t++){
sorted[k] = data[t];
k++;
}
}
// 정려된 데이터를 실제 배열에 삽입! (실제 배열을 바로 바꾸면 안된다!)
for(int t=m; t<=n; t++){
data[t] = sorted[t];
}
}
void mergeSort(int data[], int m, int n){
// 크기가 1보다 큰 경우
if(m < n){
int middle = (m+n) /2;
/* 일단 둘로 계속 나누는 mergeSort를 진행 */
mergeSort(data, m, middle);
mergeSort(data, middle+1, n);
/* 합치는 과정! */
merge(data, m, middle, n);
}
}
int main(){
int N = 10, array[10]={10,6,7,5,3,1,4,6,8,9};
mergeSort(array, 0, N-1);
for (auto a : array){
cout << a << endl;
}
}
ヒップ位置合わせ(Heap Sort)
「heapツリー構造」(Heap Tree Structure)でソートする方法
[説明]
複数のツリーが存在しますが、値が空ではない「バイナリツリー」と呼ばれます.
濃密な構造を保つ「完全バイナリツリー」を用いた構造は「hipツリー構造」である.
[最大ヒップ]:親ノードが子ノードより大きいヒップ!
[最小ヒップ]:親ノードが子ノードのヒップより小さい!
[臀部生成アルゴリズム]
:hip構造を作成するためのHeapifyアルゴリズムと呼ばれるアルゴリズム
(O(logN)の時間的複雑度-->N/2要素に対して-->O(N*logN)の時間的複雑度)
(上から下へのヒップ構造の作成-->方向の違い!(結果としてヒップ構造が変更される場合があります)
[原理]
1.配列を使用して、整列する要素をバイナリツリーとして表示
2.Hip構造の作成(Heapifyアルゴリズムを使用)
3.ルートと最後の要素の変更
4.2～3回繰り返し、最後に最大値を1つずつ入力
[コード]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
// 최초 최대 Heap 구조로 만들기 위한 Heapify 알고리즘
for(int i=1; i<N ; i++){
int c=i;
do{
int root = (c-1)/2;
if(heap[root] < heap[c]){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
}while(c != 0);
}
// 크기를 줄여가며 반복적으로 heap을 구성!
for(int i=N-1;i>=0;i--){
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
// 다시 최대 heap구조를 만들기 위한 Heapify 알고리즘
int root = 0;
int c = 1;
do{
c = 2*root + 1;
// 자식 중 더 큰 값을 찾기
if(heap[c] < heap[c+1] && c < i-1){
c++;
}
// 루트보다 자식이 더 크다면 교환
if(heap[root] < heap[c] && c < i){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
}while(c < i);
}
for(auto a : heap){
cout << a << ' ';
}
}
ソート数
与えられたデータが大きいときにO(N)時間の複雑さをソートする方法
(必要なメモリはデータの最大容量と同じなので効率が悪い)
[コード]
#include <iostream>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
int count[5];
int array[30] = {
1,3,2,4,3,2,5,3,1,2,
3,4,4,3,5,1,2,3,4,2,
3,1,4,3,5,1,2,1,1,1
};
fill(count, count+5, 0);
for(int i=0;i<30;i++){
count[array[i]-1]++;
}
for(int i=0; i<5; i++){
if(count[i] != 0){
for(int j=0; j<count[i];j++)
{
cout << i+1;
}
}
}
}
Reference
この問題について(Algorithmソートのクリア(Sort)), 我々は、より多くの情報をここで見つけました
https://velog.io/@neity16/Algorithm-정렬Sort-정리
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
using namespace std;
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
for(int i=N-1;i>0;i--)
{
for(int j=0;j<i;j++)
{
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for (auto a : arr){
cout << a << endl;
}
}位置合わせ値に対する現在の要素の位置合わせを検索して挿入します.
1)アレイの2番目の要素から
2)前の要素と比較して大きくなるまで交換する
3)ループが長ければ長いほど前の要素が整然としている
4)手順1～3を繰り返す
[時間複雑度]-O(N^2)
:O(N^2)時間の複雑さを持つソートで最も効率的
(全て比較する必要がないので)
#include <iostream>
using namespace std;
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9},j;
for(int i=1;i<N;i++)
{
j = i;
while(arr[j] < arr[j-1])
{
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
j--;
}
}
for (auto a : arr){
cout << a << endl;
}
}クイックソート
ピボットを2つのセットに分割してソートします.
[時間複雑度]-O(N*logN)
ピボット位置によって最悪の場合の複雑さはO(N^2)(最大の欠点)
(平均複雑度O(N*logN)
(最悪の場合は=>ソート済み)
(既にソートされている場合は、前述の「ソートの挿入」が有効です!)#include <iostream>
using namespace std;
void quickSort(int* data, int start, int end){
if(start >= end){
return;
}
int key = start; // 피봇 값
int i = start + 1;
int j = end;
int tmp;
while(i <= j){ // i와 j값이 엇갈릴 때 까지 수행
while(data[key] >= data[i]){ // 피봇보다 작은값을 찾을 때 까지
i++;
}
while(data[key] <= data[j] && j > start){ // 피봇보다 큰 값을 찾을 때 까지
j--;
}
if(i <= j){ // 엇갈리지 않았다면 그냥 교환
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}else{ // 엇갈렸다면 key값과 j와 교환
tmp = data[key];
data[key] = data[j];
data[j] = tmp;
}
}
quickSort(data, start, j-1);
quickSort(data,j+1, end);
}
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
quickSort(arr, 0, N-1);
for (auto a : arr){
cout << a << endl;
}
}
連結ソート
まず、ペアリングを続け、ソートをマージします.
(並べ替えられた2つの集合をマージするにはO(N)!
[時間複雑度]-O(N*logN)
#include <iostream>
using namespace std;
int N = 10, sorted[10];
// 두 묶음을 하나로 합치는 과정
void merge(int data[], int m, int middle, int n){
int i=m;
int j=middle+1;
int k=m;
// 두 집합의 값을 비교하며 차례대로 넣는 과정
while(i <= middle && j <= n){
if(data[i] <= data[j]){
sorted[k] = data[i];
i++;
}else{
sorted[k] = data[j];
j++;
}
k++;
}
// 둘 중 남은 한 집합을 마저 더해주는 과정
if(i > middle){
for(int t=j; t<=n; t++){
sorted[k] = data[t];
k++;
}
}else{
for(int t=i; t<=middle; t++){
sorted[k] = data[t];
k++;
}
}
// 정려된 데이터를 실제 배열에 삽입! (실제 배열을 바로 바꾸면 안된다!)
for(int t=m; t<=n; t++){
data[t] = sorted[t];
}
}
void mergeSort(int data[], int m, int n){
// 크기가 1보다 큰 경우
if(m < n){
int middle = (m+n) /2;
/* 일단 둘로 계속 나누는 mergeSort를 진행 */
mergeSort(data, m, middle);
mergeSort(data, middle+1, n);
/* 합치는 과정! */
merge(data, m, middle, n);
}
}
int main(){
int N = 10, array[10]={10,6,7,5,3,1,4,6,8,9};
mergeSort(array, 0, N-1);
for (auto a : array){
cout << a << endl;
}
}
ヒップ位置合わせ(Heap Sort)
「heapツリー構造」(Heap Tree Structure)でソートする方法
[説明]
複数のツリーが存在しますが、値が空ではない「バイナリツリー」と呼ばれます.
濃密な構造を保つ「完全バイナリツリー」を用いた構造は「hipツリー構造」である.
[最大ヒップ]:親ノードが子ノードより大きいヒップ!
[最小ヒップ]:親ノードが子ノードのヒップより小さい!
[臀部生成アルゴリズム]
:hip構造を作成するためのHeapifyアルゴリズムと呼ばれるアルゴリズム
(O(logN)の時間的複雑度-->N/2要素に対して-->O(N*logN)の時間的複雑度)
(上から下へのヒップ構造の作成-->方向の違い!(結果としてヒップ構造が変更される場合があります)
[原理]
1.配列を使用して、整列する要素をバイナリツリーとして表示
2.Hip構造の作成(Heapifyアルゴリズムを使用)
3.ルートと最後の要素の変更
4.2～3回繰り返し、最後に最大値を1つずつ入力
[コード]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
// 최초 최대 Heap 구조로 만들기 위한 Heapify 알고리즘
for(int i=1; i<N ; i++){
int c=i;
do{
int root = (c-1)/2;
if(heap[root] < heap[c]){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
}while(c != 0);
}
// 크기를 줄여가며 반복적으로 heap을 구성!
for(int i=N-1;i>=0;i--){
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
// 다시 최대 heap구조를 만들기 위한 Heapify 알고리즘
int root = 0;
int c = 1;
do{
c = 2*root + 1;
// 자식 중 더 큰 값을 찾기
if(heap[c] < heap[c+1] && c < i-1){
c++;
}
// 루트보다 자식이 더 크다면 교환
if(heap[root] < heap[c] && c < i){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
}while(c < i);
}
for(auto a : heap){
cout << a << ' ';
}
}
ソート数
与えられたデータが大きいときにO(N)時間の複雑さをソートする方法
(必要なメモリはデータの最大容量と同じなので効率が悪い)
[コード]
#include <iostream>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
int count[5];
int array[30] = {
1,3,2,4,3,2,5,3,1,2,
3,4,4,3,5,1,2,3,4,2,
3,1,4,3,5,1,2,1,1,1
};
fill(count, count+5, 0);
for(int i=0;i<30;i++){
count[array[i]-1]++;
}
for(int i=0; i<5; i++){
if(count[i] != 0){
for(int j=0; j<count[i];j++)
{
cout << i+1;
}
}
}
}
Reference
この問題について(Algorithmソートのクリア(Sort)), 我々は、より多くの情報をここで見つけました
https://velog.io/@neity16/Algorithm-정렬Sort-정리
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
using namespace std;
void quickSort(int* data, int start, int end){
if(start >= end){
return;
}
int key = start; // 피봇 값
int i = start + 1;
int j = end;
int tmp;
while(i <= j){ // i와 j값이 엇갈릴 때 까지 수행
while(data[key] >= data[i]){ // 피봇보다 작은값을 찾을 때 까지
i++;
}
while(data[key] <= data[j] && j > start){ // 피봇보다 큰 값을 찾을 때 까지
j--;
}
if(i <= j){ // 엇갈리지 않았다면 그냥 교환
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}else{ // 엇갈렸다면 key값과 j와 교환
tmp = data[key];
data[key] = data[j];
data[j] = tmp;
}
}
quickSort(data, start, j-1);
quickSort(data,j+1, end);
}
int main(){
int N = 10, arr[10]={10,6,7,5,3,1,4,6,8,9};
quickSort(arr, 0, N-1);
for (auto a : arr){
cout << a << endl;
}
}まず、ペアリングを続け、ソートをマージします.
(並べ替えられた2つの集合をマージするにはO(N)![時間複雑度]-O(N*logN)
#include <iostream>
using namespace std;
int N = 10, sorted[10];
// 두 묶음을 하나로 합치는 과정
void merge(int data[], int m, int middle, int n){
int i=m;
int j=middle+1;
int k=m;
// 두 집합의 값을 비교하며 차례대로 넣는 과정
while(i <= middle && j <= n){
if(data[i] <= data[j]){
sorted[k] = data[i];
i++;
}else{
sorted[k] = data[j];
j++;
}
k++;
}
// 둘 중 남은 한 집합을 마저 더해주는 과정
if(i > middle){
for(int t=j; t<=n; t++){
sorted[k] = data[t];
k++;
}
}else{
for(int t=i; t<=middle; t++){
sorted[k] = data[t];
k++;
}
}
// 정려된 데이터를 실제 배열에 삽입! (실제 배열을 바로 바꾸면 안된다!)
for(int t=m; t<=n; t++){
data[t] = sorted[t];
}
}
void mergeSort(int data[], int m, int n){
// 크기가 1보다 큰 경우
if(m < n){
int middle = (m+n) /2;
/* 일단 둘로 계속 나누는 mergeSort를 진행 */
mergeSort(data, m, middle);
mergeSort(data, middle+1, n);
/* 합치는 과정! */
merge(data, m, middle, n);
}
}
int main(){
int N = 10, array[10]={10,6,7,5,3,1,4,6,8,9};
mergeSort(array, 0, N-1);
for (auto a : array){
cout << a << endl;
}
}ヒップ位置合わせ(Heap Sort)
「heapツリー構造」(Heap Tree Structure)でソートする方法
[説明]
複数のツリーが存在しますが、値が空ではない「バイナリツリー」と呼ばれます.
濃密な構造を保つ「完全バイナリツリー」を用いた構造は「hipツリー構造」である.
[最大ヒップ]:親ノードが子ノードより大きいヒップ!
[最小ヒップ]:親ノードが子ノードのヒップより小さい!
[臀部生成アルゴリズム]
:hip構造を作成するためのHeapifyアルゴリズムと呼ばれるアルゴリズム
(O(logN)の時間的複雑度-->N/2要素に対して-->O(N*logN)の時間的複雑度)
(上から下へのヒップ構造の作成-->方向の違い!(結果としてヒップ構造が変更される場合があります)
[原理]
1.配列を使用して、整列する要素をバイナリツリーとして表示
2.Hip構造の作成(Heapifyアルゴリズムを使用)
3.ルートと最後の要素の変更
4.2～3回繰り返し、最後に最大値を1つずつ入力
[コード]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
// 최초 최대 Heap 구조로 만들기 위한 Heapify 알고리즘
for(int i=1; i<N ; i++){
int c=i;
do{
int root = (c-1)/2;
if(heap[root] < heap[c]){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
}while(c != 0);
}
// 크기를 줄여가며 반복적으로 heap을 구성!
for(int i=N-1;i>=0;i--){
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
// 다시 최대 heap구조를 만들기 위한 Heapify 알고리즘
int root = 0;
int c = 1;
do{
c = 2*root + 1;
// 자식 중 더 큰 값을 찾기
if(heap[c] < heap[c+1] && c < i-1){
c++;
}
// 루트보다 자식이 더 크다면 교환
if(heap[root] < heap[c] && c < i){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
}while(c < i);
}
for(auto a : heap){
cout << a << ' ';
}
}
ソート数
与えられたデータが大きいときにO(N)時間の複雑さをソートする方法
(必要なメモリはデータの最大容量と同じなので効率が悪い)
[コード]
#include <iostream>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
int count[5];
int array[30] = {
1,3,2,4,3,2,5,3,1,2,
3,4,4,3,5,1,2,3,4,2,
3,1,4,3,5,1,2,1,1,1
};
fill(count, count+5, 0);
for(int i=0;i<30;i++){
count[array[i]-1]++;
}
for(int i=0; i<5; i++){
if(count[i] != 0){
for(int j=0; j<count[i];j++)
{
cout << i+1;
}
}
}
}
Reference
この問題について(Algorithmソートのクリア(Sort)), 我々は、より多くの情報をここで見つけました
https://velog.io/@neity16/Algorithm-정렬Sort-정리
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
// 최초 최대 Heap 구조로 만들기 위한 Heapify 알고리즘
for(int i=1; i<N ; i++){
int c=i;
do{
int root = (c-1)/2;
if(heap[root] < heap[c]){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
}while(c != 0);
}
// 크기를 줄여가며 반복적으로 heap을 구성!
for(int i=N-1;i>=0;i--){
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
// 다시 최대 heap구조를 만들기 위한 Heapify 알고리즘
int root = 0;
int c = 1;
do{
c = 2*root + 1;
// 자식 중 더 큰 값을 찾기
if(heap[c] < heap[c+1] && c < i-1){
c++;
}
// 루트보다 자식이 더 크다면 교환
if(heap[root] < heap[c] && c < i){
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
}while(c < i);
}
for(auto a : heap){
cout << a << ' ';
}
}与えられたデータが大きいときにO(N)時間の複雑さをソートする方法
(必要なメモリはデータの最大容量と同じなので効率が悪い)
[コード]
#include <iostream>
using namespace std;
int N = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6};
int main(){
int count[5];
int array[30] = {
1,3,2,4,3,2,5,3,1,2,
3,4,4,3,5,1,2,3,4,2,
3,1,4,3,5,1,2,1,1,1
};
fill(count, count+5, 0);
for(int i=0;i<30;i++){
count[array[i]-1]++;
}
for(int i=0; i<5; i++){
if(count[i] != 0){
for(int j=0; j<count[i];j++)
{
cout << i+1;
}
}
}
}Reference
この問題について(Algorithmソートのクリア(Sort)), 我々は、より多くの情報をここで見つけました https://velog.io/@neity16/Algorithm-정렬Sort-정리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol