# 15) [C/C++] 퀵 정렬(quick sort) 알고리즘

배열 기본 예제

#include <iostream>

int main()
{
	int SortData[] = {
		20, 25, 82, 48, 49, 29, 98, 77, 45, 32
	};
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");
}

[오름차순]

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// 오름차순
int QuickSort1(const void *arg1, const void *arg2 ) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p1 - *p2);
}

int main()
{
	int SortData[] = {
		20, 25, 82, 48, 49, 29, 98, 77, 45, 32
	};
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	// 정렬의 옵션을 정의한 함수 이름
	// 정렬 해주는 함수
	// 10: 정렬한 개수, int: 정렬할 타입, 정랼할 함수: QuickSort1
	qsort(SortData, 10, sizeof(int), QuickSort1 ); // quick Sort
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");
}

[내림차순]

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// 오름차순
int QuickSort2(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p2 - *p1);
}

int main()
{
	int SortData[] = {
		20, 25, 82, 48, 49, 29, 98, 77, 45, 32
	};
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	// 정렬의 옵션을 정의한 함수 이름
	// 정렬 해주는 함수
	// 10: 정렬한 개수, int: 정렬할 타입, 정랼할 함수: QuickSort2
	qsort(SortData, 10, sizeof(int), QuickSort2); // quick Sort2
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");
}

[순차정렬]

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// ( > ) 순차정렬
int QuickSort3(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	if (*p1 > *p2) {
		return +1;
	}
	else {
		return -1;
	}
	// 삼항연산자로 바꾼다면
	// return(*p1 > *p2) ? +1 : -1;
}

int main()
{
	int SortData[] = {
		20, 25, 82, 48, 49, 29, 98, 77, 45, 32
	};
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	// 정렬의 옵션을 정의한 함수 이름
	// 정렬 해주는 함수
	// 10: 정렬한 개수, int: 정렬할 타입, 정랼할 함수: QuickSort3
	qsort(SortData, 10, sizeof(int), QuickSort3); // quick Sort3
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");
}

[역순정렬]

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// ( < ) 역순정렬
int QuickSort3(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	if (*p1 < *p2) {
		return +1;
	}
	else {
		return -1;
	}
	// 삼항연산자로 바꾼다면
	// return(*p1 < *p2) ? +1 : -1;
}

int main()
{
	int SortData[] = {
		20, 25, 82, 48, 49, 29, 98, 77, 45, 32
	};
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	// 정렬의 옵션을 정의한 함수 이름
	// 정렬 해주는 함수
	// 10: 정렬한 개수, int: 정렬할 타입, 정랼할 함수: QuickSort3
	qsort(SortData, 10, sizeof(int), QuickSort3); // quick Sort3
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");
}

[전체 코드]

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// 오름차순
int QuickSort1(const void *arg1, const void *arg2 ) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p1 - *p2);
}

// 내림차순
int QuickSort2(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p2 - *p1);
}

// ( > ) 순차정렬
// ( < ) 역순정렬
int QuickSort3(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	if (*p1 > *p2) {
		return +1;
	}
	else {
		return -1;
	}
	// 삼항연산자로 바꾼다면
	// return(*p1 > *p2) ? +1 : -1;
}

int main()
{
	int SortData[] = {
		20, 25, 82, 48, 49, 29, 98, 77, 45, 32
	};
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	// 정렬의 옵션을 정의한 함수 이름
	// 정렬 해주는 함수
	// 10: 정렬한 개수, int: 정렬할 타입, 정랼할 함수: QuickSort1
	qsort(SortData, 10, sizeof(int), QuickSort1 ); // quick Sort1
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	qsort(SortData, 10, sizeof(int), QuickSort2); // quick Sort2
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");

	qsort(SortData, 10, sizeof(int), QuickSort3); // quick Sort3
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", SortData[i]);
	}
	printf("\n");
}

[구조체 추가]

index를 기준으로 정렬을 할 것이다.

index를 정렬 시키면 뒤에 있는 데이터들이 다 따라온다.

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// 오름차순
int QuickSort1(const void *arg1, const void *arg2 ) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p1 - *p2);
}

// 내림차순
int QuickSort2(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p2 - *p1);
}

// ( > ) 순차정렬
// ( < ) 역순정렬
int QuickSort3(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	if (*p1 > *p2) {
		return +1;
	}
	else {
		return -1;
	}
	// 삼항연산자로 바꾼다면
	// return(*p1 > *p2) ? +1 : -1;
}

struct STRU {
	int index;
	int data[3];
};


#include "time.h"
int main()
{
	srand((unsigned)time(NULL));

	STRU DataInfo[6];
	for (int i = 0; i < 6; i++)	
	{
		DataInfo[i].index = rand() % 10;
		
		for (int j = 0; j < 3; j++)
		{
			DataInfo[i].data[j] = rand() % 50 + 50;
		}
	}

	// 출력
	for (int i = 0; i < 6; i++)
	{
		printf("%d : ", DataInfo[i].index);

		for (int j = 0; j < 3; j++)
		{
			printf("%d : ", DataInfo[i].data[j]);
		}
		printf("\n");
	}
	printf("\n");
}

[정렬 후]

#include <iostream>
#include <windows.h>


// 정렬의 조건을 만들어 주는 함수
// 오름차순
int QuickSort1(const void *arg1, const void *arg2 ) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p1 - *p2);
}

// 내림차순
int QuickSort2(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	// (앞의 인수 - 뒤의 인수)라는 표현을 사용하게되면 슌차정렬을 하라는 것.
	return (*p2 - *p1);
}

// ( > ) 순차정렬
// ( < ) 역순정렬
int QuickSort3(const void *arg1, const void *arg2) {
	int *p1 = (int*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	int *p2 = (int*)arg2;	// arg2를 int타입의 주소로 봐라

	if (*p1 > *p2) {
		return +1;
	}
	else {
		return -1;
	}
	// 삼항연산자로 바꾼다면
	// return(*p1 > *p2) ? +1 : -1;
}

struct STRU {
	int index;
	int data[3];
};

int QuickSort4(const void *arg1, const void *arg2) {
	STRU *p1 = (STRU*)arg1;	// arg1를 int타입의 주소로 봐라 (주소전달, 값전달)
	STRU *p2 = (STRU*)arg2;	// arg2를 int타입의 주소로 봐라
	
	return (p1->index - p2->index);
}

#include "time.h"
int main()
{
	srand((unsigned)time(NULL));

	STRU DataInfo[6];
	for (int i = 0; i < 6; i++)	
	{
		DataInfo[i].index = rand() % 10;
		
		for (int j = 0; j < 3; j++)
		{
			DataInfo[i].data[j] = rand() % 50 + 50;
		}
	}

	// 출력
	for (int i = 0; i < 6; i++)
	{
		printf("%d : ", DataInfo[i].index);

		for (int j = 0; j < 3; j++)
		{
			printf("%d : ", DataInfo[i].data[j]);
		}
		printf("\n");
	}
	printf("\n");

	qsort(DataInfo, 6, sizeof(STRU), QuickSort4);

	//  정렬 후
	for (int i = 0; i < 6; i++)
	{
		printf("%d : ", DataInfo[i].index);

		for (int j = 0; j < 3; j++)
		{
			printf("%d : ", DataInfo[i].data[j]);
		}
		printf("\n");
	}
	printf("\n");
}

---

[문제: 프로야구 승률에 따른 역순정렬]

프로야구 5개 구단

팀      전    승    무    패    승률

삼성   40    22    2    16               

엘지

현대

한화

롯데

 

** 조건: (승률 = 승/전)  2회무승부 = 1승

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <Windows.h>
#include <time.h>
#include <math.h>
struct STRUBASEBALL
{
	char Team[10] = { 0, };
	int win = 0;
	int draw = 0;
	int lose = 0;
};
int QuickSortPlay(const void* arg1, const void* arg2)
{
	STRUBASEBALL* p1 = (STRUBASEBALL*)arg1;
	STRUBASEBALL* p2 = (STRUBASEBALL*)arg2;
	return (p2->win - p1->win);
}
int main()
{
	//STRUBASEBALL samsung, LG, HanHwa, Lotte, SK;
	srand((unsigned)time(NULL));
	STRUBASEBALL Game[5];
	for (int i = 0; i < 5; i++)
	{
		for (int j = i + 1; j < 5; j++)
		{
			for (int n = 0; n < 10; n++)
			{
				int rate = rand() % 100;
				if (rate >= 55)
				{
					Game[i].win++;
					Game[j].lose++;
				}
				else if (rate <= 45)
				{
					Game[i].lose++;
					Game[j].win++;
				}
				else
				{
					Game[i].draw++;
					Game[j].draw++;
				}
			}
		}
		switch (i)
		{
		case 0:
			strcpy(Game[i].Team, "SamSung");
			break;
		case 1:
			strcpy(Game[i].Team, "LG");
			break;
		case 2:
			strcpy(Game[i].Team, "Lotte");
			break;
		case 3:
			strcpy(Game[i].Team, "Doosan");
			break;
		case 4:
			strcpy(Game[i].Team, "KT");
			break;
		}
	}

	for (int i = 0; i < 5; i++)
	{
		printf("%s\t => win : %d || draw : %d || lose : %d\n", 
			Game[i].Team, Game[i].win, Game[i].draw, Game[i].lose);
	} printf("\n");
	qsort(Game, 5, sizeof(STRUBASEBALL), QuickSortPlay);
	
	
	for (int i = 0; i < 5; i++)
	{
		float winrate;
		winrate = ((Game[i].win + (Game[i].draw % 2)) / 40.f) * 100.f;
		printf("%s\t => win : %d || draw : %d || lose : %d || winrate : %0.2f%%\n",
			Game[i].Team, Game[i].win, Game[i].draw, Game[i].lose, winrate);
	}
}