백준_2751

quick sort + pivot 을 매개변수로 받지않고 left+right/2로  -> 통과

// #2751 수 정렬하기 2
// 입력 : 첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다.
// 이 수는 절대값이 1,000,000보다 작거나 가은 정수이다. 수는 중복되지 않는다.
// 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

// Quick Sort 로 해볼꺼야!
#define _CRT_SECURE_NO_WARNINGS
#include
#include

void QuickSort(int *p, int start_idx, int end_idx) {
	int l = start_idx, r = end_idx;
	int pivot = p[(l+r)/2];

	while (l <= r) {
		while (pivot > p[l]) {
			l++;
		}
		while (pivot < p[r]) {
			r--;
		}
		if (l <= r) {
			//swap l,r
			int temp = p[l];
			p[l] = p[r];
			p[r] = temp;
			l++, r--;
		}
	}
	if (start_idx < r) QuickSort(p, start_idx, r);
	if (l < end_idx) QuickSort(p, l, end_idx);
}

int main(void) {
	int n; // 수의 개수
	int *array;

	scanf("%d",&n);

	array = (int *)malloc(sizeof(int)*n); // 동적배열

	for (int j = 0; j < n; j++) {
		
		scanf("%d", &array[j]);
	}

	//QuickSort(int *p,int pivot,int start_idx,int end_idx);
	QuickSort(array, 0, n - 1);  // &array아니고 array로 보내야함

	for (int j = 0; j < n; j++) {
		printf("%d\n", array[j]);
	}

	getch();
	return 0;
}

quick sort -> 런타임 에러

// Quick Sort 로 해볼꺼야!

#define _CRT_SECURE_NO_WARNINGS

#include

#include



void QuickSort(int *p,int pivot, int start_idx, int end_idx) {

	int l = start_idx, r = end_idx;

	while (l <= r) {

		while (p[pivot] >= p[l]) {

			l++;

		}

		while (p[pivot] < p[r]) {

			r--;

		}

		if (lr

			// swap r,pivot

			int temp = p[pivot];

			p[pivot] = p[r];

			p[r] = temp;



			QuickSort(p,pivot,pivot+1,r-1);   // p 어떻게 보내줘야할지 모르겠어

			QuickSort(p,r+1,r+2,end_idx);

		}

	}

}



int main(void) {

	int n; // 수의 개수

	int *array;



	scanf("%d",&n);



	array = (int *)malloc(sizeof(int)*n); // 동적배열



	for (int j = 0; j < n; j++) {

		

		scanf("%d", &array[j]);

	}



	//QuickSort(int *p,int pivot,int start_idx,int end_idx);

	QuickSort(array, 0, 1, n - 1);  // &array아니고 array로 보내야함



	for (int j = 0; j < n; j++) {

		printf("%d\n", array[j]);

	}



	getch();

	return 0;

}

selection sort -> 시간초과

// Selection Sort 로 해볼꺼야!

#define _CRT_SECURE_NO_WARNINGS

#include

#include



int WhoIsSmallest(int *p,int start_idx,int sz) {

	int smallest_idx = start_idx;

	int smallest = p[start_idx];



	for (int i = (start_idx+1); i < sz; i++) {

		if (smallest > p[i]) {

			smallest = p[i];

			smallest_idx = i;

		}

	}

	return smallest_idx;

}



void swap(int *p, int a, int b) {

	int temp = p[a];

	p[a] = p[b];

	p[b] = temp;

}



int main(void) {

	int n; // 수의 개수

	int *array;



	scanf("%d",&n);



	array = (int *)malloc(sizeof(int)*n); // 동적배열



	for (int j = 0; j < n; j++) {

		

		scanf("%d", &array[j]);

	}



	for (int i = 0; i < n; i++) {

		int temp = WhoIsSmallest(array, i, n);

		swap(array,i,temp);

	}



	for (int j = 0; j < n; j++) {

		printf("%d\n", array[j]);

	}



	//getch();

	return 0;

}