반응형
#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
#define SHUFFLE_MAX 100///< 최대 교환 횟수
#define MAX_ARRAY 10 ///< 최대 배열 개수
===================================
#pragma once
class cSort
{
public:
cSort(void);
~cSort(void);
///< 오름 차순 : ascending sort(어센딩)
///< 내림 차순 : descending sort(디센딩)
///< 함수 포인터를 이용한 교환
typedef void(*SortFuncPtr)(int&, int&);
///< 버블정렬
void Sort_Bubble(int* pArray, int nArraySize, bool bIsAscending = false );
///< 개선된 버블정렬
void Sort_Bubble_Improve(int* pArray, int nArraySize, bool bIsAscending = false);
///< 선택정렬
void Sort_Select(int* pArray, int nArraySize, bool bIsAscending = false);
///< 개선된 선택정렬
void Sort_Select_Improve(int* pArray, int nArraySize, bool bIsAscending = false);
///< 삽입정렬
void Sort_Insert(int* pArray, int nArraySize, bool bIsAscending = false);
///< 쉘정렬(개선된 삽입이라고 볼수있다)
void ShellSort(int* pArray, int nArraySize, bool bIsAscending = false);
///< 퀵정렬
void Sort_Quick(int* pArray, int nArraySize, bool bIsAscending = false);
///< 퀵정렬 관련
void Quick(int* pArray, int nArraySize, int nLeft, int nRight , bool bIsAscending);
void quick_sort(int a[], int left, int right) ;
///< 랜덤하게 번호생성(전달 개수 만큼)
void InitArrayNumber(int* pArray, int nArraySize);
///< 번호 교환
void SwapNumber(int& nDest , int& nSrc);
///< 소팅 전후 비교
void OutputBeforeSort(int* pArray, int nArraySize);
void OutputAfterSort(int* pArray, int nArraySize);
///< 출력
void OutputArray(int* pArray, int nArraySize);
///< 두수의 대소 비교후 교환
void AscendingSwap(int& nLeft , int& nRight);
void DescendingSwap(int& nLeft, int& nRight);
};
===========================================================
#include "StdAfx.h"
#include "cSort.h"
cSort::cSort(void)
{
}
cSort::~cSort(void)
{
}
///< 버블정렬
void cSort::Sort_Bubble(int* pArray, int nArraySize, bool bIsAscending)
{
/*
인접한 두원소를 비교해서 정렬하는 가장 간단한 정렬방법이다.
시간복잡도 : O = n^2;
구현이 간단하며 원소의 정렬과정이 거품이 수면으로 떠오르는 방법과
유사하다 하여 버블정렬이라한다.
가장 유의할 점은 index 가 0 , +1을 비교하기 때문에 배열의 최대를 벗어날수 있다.
ARRAY_MAX -1 까지 비교해야 하는점을 유의하자.
장점으로는 구현이 쉽다는점이 있다.
단점으로는 정렬중 가장 느리다.
*/
///< 번호 랜덤하게 생성
cout << endl << "Bubble Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
///< 함수 포인터를 이용한 정렬함수(^^)
///< 오름 차순 정렬 이라면
//SortFuncPtr pSwapFunc = NULL;
//if( bIsAscending == true )
//{
// pSwapFunc = AscendingSwap;
//}
//else
//{
// pSwapFunc = DescendingSwap;
//}
for(int i = 0; i < nArraySize - 1; i++)
{
cout <<"index : " << i << endl;
for(int j = 0; j < nArraySize - 1; j++)
{
///< 인자로 비교해서 정렬
if( bIsAscending == true )
{
///< 오름 차순
if( pArray[j] > pArray[j+1])
{
SwapNumber(pArray[j],pArray[j+1]);
}
}
else
{
///< 오름 차순
if( pArray[j] < pArray[j+1])
{
SwapNumber(pArray[j],pArray[j+1]);
}
}
///< 함수 포인터를 이용해서 오름 차순 / 내림 차순을 결정한다.
//pSwapFunc(pArray[j],pArray[j+1]);
//OutputArray(pArray,nArraySize);
//cout << endl;
}
OutputArray(pArray,nArraySize);
}
///< 소팅후 출력
OutputAfterSort(pArray,nArraySize);
}
///< 개선된 버블정렬
void cSort::Sort_Bubble_Improve(int* pArray, int nArraySize, bool bIsAscending)
{
/*
기존의 버블정렬은 이미 정렬이 완료되었더라도 인접한 수를 비교하기 때문에
0 : n^2으로 시간복잡도가 발생한다.
개선된 버블정렬은 이미 완료된 곳은 정렬에서 제외하며 flag를 처리하여
모두 완료되었다면 더이상 비교를 하지않도록 기존의 버블정렬을 개선한 형태이다.
기존의 버블정렬에서의 단점을 보완한 형태이다.
*/
///< 번호 랜덤하게 생성
cout << endl << "Bubble Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
for(int i = 0; i < nArraySize - 1; i++)
{
bool bComplet = true;
cout <<"index : " << i << endl;
for(int j = 0; j < nArraySize - 1 - i; j++)
{
///< 인자로 비교해서 정렬
if( bIsAscending == true )
{
///< 오름 차순
if( pArray[j] > pArray[j+1])
{
SwapNumber(pArray[j],pArray[j+1]);
bComplet = false;
}
}
else
{
///< 오름 차순
if( pArray[j] < pArray[j+1])
{
SwapNumber(pArray[j],pArray[j+1]);
bComplet = false;
}
}
///< 함수 포인터를 이용해서 오름 차순 / 내림 차순을 결정한다.
}
OutputArray(pArray,nArraySize);
if( bComplet == true )
{
cout <<"정렬이 완료어서 종료 합니다 " <<endl;
break;
}
}
///< 소팅후 출력
OutputBeforeSort(pArray,nArraySize);
}
///< 선택정렬
void cSort::Sort_Select(int* pArray, int nArraySize, bool bIsAscending)
{
/*
가장 단순한 정렬 방법중이다.
최소값을 찾아 앞쪽으로 이동하면서 정렬을 완료하는 기법으로
해당 배열의 크기만큼 반복적으로 수행한다.
배열에서 가장 작은 값을 찾아 선택된 인덱스와 교환하는 방법이다.
정렬되는 과정은
주어진 리스트중 최소값을 찾는다.
선택된 인덱스와 교환한다(swap)
배열의 사이즈 만큼 반복한다.
*/
///< 번호 랜덤하게 생성
cout << endl << "Select Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
for(int i = 0; i < nArraySize - 1; i++)
{
for(int j = i + 1; j < nArraySize; j++)
{
///< 인자로 비교해서 정렬
if( bIsAscending == true )
{
///< 오름 차순
if( pArray[i] > pArray[j])
{
SwapNumber(pArray[i],pArray[j]);
}
}
else
{
///< 오름 차순
if( pArray[i] < pArray[j])
{
SwapNumber(pArray[i],pArray[j]);
}
}
}
OutputArray(pArray,nArraySize);
cout << endl;
}
///< 소팅후 출력
OutputBeforeSort(pArray,nArraySize);
}
///< 개선된 선택정렬
void cSort::Sort_Select_Improve(int* pArray, int nArraySize, bool bIsAscending)
{
/*
개선된 선택정렬은 선택된 인덱스와 매번 비교해서 교환하는 방법에서
교환될 인덱스만 기억해서 교환하는 방법으로 교체에 걸리는 시간을
최소화 시키는 기법이다.
*/
///< 번호 랜덤하게 생성
cout << endl << "Select Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
for(int i = 0; i < nArraySize - 1; i++)
{
int nSortIndex = i;
for(int j = i + 1; j < nArraySize; j++)
{
///< 인자로 비교해서 정렬
if( bIsAscending == true )
{
///< 오름 차순
if( pArray[nSortIndex] > pArray[j])
{
nSortIndex = j;
}
}
else
{
///< 오름 차순
if( pArray[nSortIndex] < pArray[j])
{
nSortIndex = j;
}
}
}
if( nSortIndex != i )
{
cout <<"SwapIndex : " << nSortIndex << endl;
cout <<"SwapNumber : " << pArray[nSortIndex]<<endl;
SwapNumber(pArray[i],pArray[nSortIndex]);
}
OutputArray(pArray,nArraySize);
cout << endl;
}
///< 소팅후 출력
OutputBeforeSort(pArray,nArraySize);
}
///< 삽입정렬
void cSort::Sort_Insert(int* pArray, int nArraySize, bool bIsAscending)
{
/*
삽입 정렬은 정렬 리스트의 모든 요소를 앞에서 부터 차례로 이미 정렬된 배열 부분과 비교하여
자신의 위치를 정하고 삽입함으로써 정렬하는 기법이다.
장점은 속도가 기존 0 :n^2나오는 정렬중 가장 빠르지만 평균 1.5정도 나온다.
단점으로는 역순으로 정리할때는 느리다는 단점이 있다.
*/
///< 번호 랜덤하게 생성
cout << endl << "Insert Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
for(int i = 1; i < nArraySize ; i++)
{
int nKey = pArray[i];
int j;
///< 삼항 연산자를 이용해서 오름차순/내림차순 정렬
for( j = i - 1;
(j >= 0) &&
( bIsAscending == true ?
nKey < pArray[j] :
nKey > pArray[j] ) ; j-- )
{
pArray[j+1] = pArray[j];
}
pArray[j+1] = nKey;
OutputArray(pArray,nArraySize);
cout << endl;
}
///< 소팅후 출력
OutputBeforeSort(pArray,nArraySize);
}
///< 개선된 삽입정렬
void cSort::ShellSort(int* pArray, int nArraySize, bool bIsAscending)
{
/*
개선된 삽입정렬에는 쉘정렬이 있다. 쉘정렬은 고안자인 Shell의 이름을 따서 만들어졌다.
쉘정렬이란 정렬할 리스트를 일정한 간격(gap)을 두고 그간격내에서만
삽입정렬을 수행하며 간격을 줄여가는 정렬 방법이다.
삽입정렬이 어느정도 정렬이 완료된 상태에서는 상당히 빠르다는 장점을 이용해서
삽입정렬을 개선한 방법이다.
삽입 정렬의 최대 문제점이 요소 들이 삽입될때 인접해서만 이동하기 때문에 만약
삽입할 위치가 많이 떨어져 있다면 많이 이동해야 하기때문에 효율이 떨어진다는 문제가 있다.
Sehll Sort는Insert Srot와는 다르게 전체리스트를 한번에 정렬하지않고 분할해서 정복하는
분할정복법이다.
먼저 정렬리스트를 일정기준에 따라 분류하고 연속적이지 않은 여러개의 리스트를 만든다.
각 부분 리스트를 Insert Sort(삽입정렬)을 이용정렬한다.
모든 부분 리스트가 정렬되면 리스트를 더 작은 간격(gap)을 설정하고 다시 정렬한다.
이러한 방법으로 간격이 1이 될때까지 반복적으로 수행하는 알고리즘이다.
Donald Shell은 처음에 간격을 2^h, (h는 0 이상의 자연수) 혹은 2^h-1로 잡았으며,
Marcin Ciura의 연구에 의하면 1, 4, 10, 23, 57, 132, 301, 701, 1750 ...의 간격으로 잡아서
실행할때 연산시간을 많이 줄인다고 한다.
예제는 h/3 로 간격을 설정하였다.
*/
///< 번호 랜덤하게 생성
cout << endl << "Shell Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
///< 증가할때는 3 * h + 1로 감소할때는 h/3으로
int h = 1;
for(int i = 1 ; h < nArraySize ; h = 3 * h + 1 );
while( h != 1)
{
h = h / 3; /// 다음 간격을 h / 3으로 구한다.
cout <<"Gap h = " << h << endl;
for(int i = h; i < nArraySize; i++)
{
int nKey = pArray[i];
int j;
///< 삼항 연산자를 이용해서 오름차순/내림차순 정렬
for( j = i - 1; (j >= 0) && (bIsAscending == true ? nKey < pArray[j] : nKey > pArray[j] ) ; j--)
{
pArray[j+1] = pArray[j];
}
pArray[j+1] = nKey;
}
OutputArray(pArray,nArraySize);
cout << endl;
}
///< 소팅후 출력
OutputBeforeSort(pArray,nArraySize);
}
///< 퀵정렬(재귀함수를 이용한 퀵정렬)
void cSort::Sort_Quick(int* pArray, int nArraySize, bool bIsAscending)
{
///< 번호 랜덤하게 생성
cout << endl << "Bubble Sort" << endl << "Initialize Array:" << endl;
InitArrayNumber(pArray,nArraySize);
///< 소팅 전 출력
OutputBeforeSort(pArray, nArraySize);
cout << endl;
Quick(pArray,nArraySize,0,nArraySize - 1,bIsAscending);
///< 소팅후 출력
OutputBeforeSort(pArray,nArraySize);
}
///< 퀵정렬 관련
void cSort::Quick(int* pArray, int nArraySize, int nLeft, int nRight , bool bIsAscending)
{
int i, j;
///< 기준값 설정
int pivot; // 기준값
///< 좌측 인덱스 설정
i = nLeft;
///< 우측 인덱스 설정
j = nRight+1 ;
///< 왼쪽값을 기준으로 설정
pivot = pArray[nLeft];
if(nLeft < nRight)
{
///< 한번은 무조건 실행해야한다.
///< 피봇을 설정하기 위해 한번은 실행해야한다.
do
{
if( bIsAscending == true )
{
while(pArray[++i] < pivot);
while(pArray[--j] > pivot);
}
else
{
while(pArray[++i] > pivot);
while(pArray[--j] < pivot);
}
if( i < j )
{
SwapNumber(pArray[i],pArray[j]);
}
} while(i < j);
pArray[nLeft] = pArray[j];
pArray[j] = pivot;
Quick(pArray, nArraySize, nLeft, j-1,bIsAscending);
Quick(pArray, nArraySize, j+1, nRight,bIsAscending);
}
}
///< 랜덤하게 번호생성(전달 개수 만큼)
void cSort::InitArrayNumber(int* pArray, int nArraySize)
{
srand((unsigned int)time(0));
///< 포인터 확인
if( pArray == NULL )
{
return;
}
///< 번호 생성
for( int i = 0 ; i< nArraySize ; i++ )
{
pArray[i] = i;
}
///< 번호 섞기
for( int i = 0 ; i < SHUFFLE_MAX; i++ )
{
int nDest = rand() %nArraySize;
int nSrc = rand() % nArraySize;
SwapNumber(pArray[nDest],pArray[nSrc]);
//SwapNumber(pArray[rand()%nArraySize],pArray[rand()%nArraySize]);
/*
위를 풀어쓰면
이렇게 두수의 랜덤한 인덱스만 뽑아내서
교환하면 이미 뽑힌 범위 내에서 교환을 하기 때문에 중복수가
발생되지 않는다.
*/
}
}
///< 번호 교환
void cSort::SwapNumber(int& nDest , int& nSrc)
{
int nTemp = nDest;
nDest = nSrc;
nSrc = nTemp;
}
///< 소팅 전후 비교
void cSort::OutputBeforeSort(int* pArray, int nArraySize)
{
cout <<"Sort Before : ";
OutputArray(pArray,nArraySize);
cout << endl;
}
void cSort::OutputAfterSort(int* pArray, int nArraySize)
{
cout <<"Sort After : ";
OutputArray(pArray,nArraySize);
cout << endl;
}
///< 출력
void cSort::OutputArray(int* pArray, int nArraySize)
{
if( pArray == NULL )
{
return;
}
for( int i = 0 ; i < nArraySize; i++ )
{
if( i == nArraySize - 1)
{
cout << pArray[i] << endl;
}
else
{
cout << pArray[i] << ",";
}
}
}
///< 두수의 대소 비교후 교환
///< 오름 차순 정렬(작은수 부터 큰수로)
void cSort::AscendingSwap(int& nLeft , int& nRight)
{
if( nLeft > nRight)
{
SwapNumber(nLeft,nRight);
}
}
///< 내림 차순 정렬(큰수부터 작은수로)
void cSort::DescendingSwap(int& nLeft, int& nRight)
{
if( nLeft < nRight )
{
SwapNumber(nLeft,nRight);
}
}
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// 01_정렬.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include "cSort.h"
int _tmain(int argc, _TCHAR* argv[])
{
cSort nSort;
int nArray[MAX_ARRAY];
///< 버블 정렬 테스트
//nSort.Sort_Bubble(nArray,MAX_ARRAY,true);
nSort.Sort_Bubble_Improve(nArray,MAX_ARRAY,true);
///< 선택 정렬 테스트
//nSort.Sort_Select(nArray,MAX_ARRAY,true);
//nSort.Sort_Select_Improve(nArray,MAX_ARRAY,true);
///< 삽입 정렬 테스트
//nSort.Sort_Insert(nArray,MAX_ARRAY,true);
//nSort.ShellSort(nArray,MAX_ARRAY,true);
///< 퀵정렬
//nSort.Sort_Quick(nArray,MAX_ARRAY,true);
//nSort.InitArrayNumber(nArray,MAX_ARRAY);
//nSort.quick_sort(nArray,0,MAX_ARRAY-1) ;
//nSort.OutputArray(nArray,MAX_ARRAY);
return 0;
}
반응형