U E D R , A S I H C RSS

새싹교실/2015/의사양반/0408



1. 참여자 명단


의사 장용운 11학번 카벅
환자 천준현 15학번 카벅
최지혁 카벅
박인서 출석

2. 수업

2.1. 진행

1. 장소 : 6층 학회실
2. 시간 : 11:30 ~ 13:00
카벅 방문으로 늦어짐

2.2. 내용

Pre-8강. Quick sort
  • 퀵소트 해부

3. 코드

3.1. 예제1

#include <stdio.h>
#pragma warning(disable:4996)

void quicksort(int*, int, int);
void printarr(int*, int, int);

int main(void) {
	int arr1[10] = { 4, 2, 1, 5, 3, 6, 2, 5, 3, 0 };
	int arr2[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int arr3[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	int arr4[10] = { 0, 1, 1, 1, 0, 3, 2, 2, 1, 0 };

	printarr(arr1, 0, 9);
	quicksort(arr1, 0, 9);
	printarr(arr1, 0, 9);
	printf("\n====================\n");

	printarr(arr2, 0, 9);
	quicksort(arr2, 0, 9);
	printarr(arr2, 0, 9);
	printf("\n====================\n");

	printarr(arr3, 0, 9);
	quicksort(arr3, 0, 9);
	printarr(arr3, 0, 9);
	printf("\n====================\n");

	printarr(arr4, 0, 9);
	quicksort(arr4, 0, 9);
	printarr(arr4, 0, 9);
	printf("\n====================\n");

	return 0;
}

void quicksort(int* arr, int s, int e) {
	if (e - s < 1) return;

	int k = s;
	int t = 0;

	for (int i = s + 1; i <= e; i++) {
		if (arr[s] > arr[i]) {
			t = arr[k + 1];
			arr[k + 1] = arr[i];
			arr[i] = t;
			k++;
		}
	}
	t = arr[k];
	arr[k] = arr[s];
	arr[s] = t;
	

	quicksort(arr, s, k - 1);
	quicksort(arr, k + 1, e);
}

void printarr(int* arr, int s, int e) {
	int i;
	printf("Printing array.... { ");
	for (i = s; i < e; i++) {
		printf("%d, ", arr[i]);
	}
	printf("%d }\n", arr[e]);
}

4. 숙제

1. 이 페이지에 후기 작성하기!
2. 오늘 공부한 개념 수업 페이지에 정리하기!
3. Quicksort 완성하기

5. 후기

  • 후기 작성 요령 : 후기는 F4(ThreeFs + Future Action Plan)에 맞게 작성해주세요.
    • Facts, Feelings, Findings, Future Action Plan. 즉, 사실, 느낀 점, 깨달은 점, 앞으로의 계획.

  • 퀵소트... 선배가 다 설명해주셨지만 멀뚱멀뚱 쳐다만 보고 아무것도 못했다는 게 현재 제 실력을 대변해주는 것 같습니다. 더 열심히 할께요 ㅠㅠ - 천준현
  • 어려웠습니다... 스스로 난 덜떨어진 놈이구나 라고 계속 생각했습니다. 시험이 이것만큼 어렵진 않기를...... - 최지혁
  • 왜 저 빼고 다 카벅...퀵소트를 구현했습니다. 힘든 점도 많았지만, 선배님이 도와주신 부분이 많아서 어렵지 않게 짤 수 있었습니다. 이보다 훨씬 어려운 것이 많기에 앞으로 더욱 노력해야겠다고 생각하였습니다. - 박인서



6. 숙제 제출

6.1. 천준현

아직도 k = s 가 왜 되어야하는지 모르겠어요. 가르쳐주세요.
#include <stdio.h>
void quicksort(int*arr, int s, int e){
	int pivot, i, j, t;
	if (e - s <= 1) return;

	pivot = arr[s];
	int k = s;
	for (i = s + 1; i <= e; i++){
		if (arr[s] > arr[i]){
			t = arr[k + 1];
			arr[k + 1] = arr[i];
			arr[i] = t;
			k++;

		}
	}

	int a;
	a = arr[s];
	arr[s] = arr[k];
	arr[k] = a;
	quicksort(arr, s, k - 1);
	quicksort(arr, k + 1, e);
}
int main(void){
	int arr[10] = { 100, 3, 139, 7, 9, 57, 4, 6, 8, 0 };
	int i;
	quicksort(arr, 0, 9);
	for (i = 0; i <= 9; i++) printf("%d\n", arr[i]);
	return 0;
}

6.2. 최지혁


#include<stdio.h>




void quicksort(int* arr, int s, int e)
{
	int i, t, pivot;
	int z;
	if (e - s < 1)
	{
		return;
	}

	int k = s;
	pivot = arr[s];
	for (i = s + 1; i <= e; i++)
	{
		if (arr[s] > arr[i])
		{
			t = arr[k + 1];
			arr[k + 1] = arr[i];
			arr[i] = t;
			k++;
		}
	}
	z = arr[s];
	arr[s] = arr[k];
	arr[k] = z;
	quicksort(arr, s, k - 1);
	quicksort(arr, k + 1, e);
}

int main()
{
	int arr[10] = { 1, 3, 5, 22, 6, 12, 451, 64, 31, 777 };

	quicksort(arr, 0, 9);

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

	return 0;

}

6.3. 박인서

  • 오늘 공부한 개념하나밖에 없지만 구현이...
퀵소트 : 특정한 한 값을 pivot으로 정하면 그 값을 기준으로 작은 값을 왼쪽에, 큰 값을 오른쪽에 놓는다. 그러고 난 뒤 작은 값, 큰 값 끼리 이 작업을 계속 반복하면서 정렬한다.
  • 코드제출

#include <stdio.h>

void quicksort(int * arr, int s, int e)
{
	int i,j,pivot,t;
	if(s>=e) return;
	pivot=s;
	for(i=s+1;i<=e;i++)
	{
		if(arr[s]>arr[i])
		{
			pivot++;
			if(arr[i]<arr[pivot])
			{
				t=arr[pivot];
				arr[pivot]=arr[i];
				arr[i]=t;
			}
		}
	}
	t=arr[pivot];
	arr[pivot]=arr[s];
	arr[s]=t;
	quicksort(arr,s,pivot-1);
	quicksort(arr,pivot+1,e);
}

int main()
{
	int i;
	int arr[20];
	for(i=0;i<=19;i++) scanf("%d",&arr[i]);
	quicksort(arr,0,19);
	for(i=0;i<=19;i++) printf("%d ",arr[i]);
	return 0;
}



Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:29:58
Processing time 0.0285 sec