Sorting 정렬

아주 오랜만에, 버블정렬, 삽입정렬, 선택정렬, 퀵정렬 을 구현했다. Merge정렬 구현하고 나면, Python 으로도 다시 구현해 봐야겠다. 

지금 생각해보니, 선택정렬을 할 때에 맨 큰 값을 셋팅하는게 아니라 제일 작은 값부터 셋팅해야 했었던 것 같긴 하다. 반대로 짠듯..

사실 지금 이거 할때가 아니고, 스웨덴 회사 코딩 시험을 쳐야 하는데.. 링크 누르기가 겁이 나서 딴 짓을 계속 하게 된다.

마치 시험 전날에 계속 책상 정리를 하고 노트를 잔득 구매하는 것 처럼..

현실 도피중이라는것을 인지 하면서도, 계속 하고 있는 내가 싫어지려고 한다.

그나저나 코드 하이라이터가 제대로 동작을 안해서 한참동안 쇼를 했다. 

HTML모드에서는 기본 tag만 입력하고, 내용은 편집기 모드로 돌아와서 작성을 해야 깨지지 않는다. 

"<" 를 "&lt;" 로 바꾸고,  ">"를 "&gt;" 바꾸기 때문인데, 나중에 시간나면 깃 들어가서 수정해봐야겠다.

hightlight.js 사이트

hightlight.js Git

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void bubleSort(int numArray[], int length);
void insertSort(int numArray[], int length);
void selectionSort(int numArray[], int length);
void mergeSort(int numArray[], int length);
void quickSort(int numArray[], int length);
void quickSortStart(int numArray[], int firstValue, int lastValue);
int quickSortFindSplit(int numArray[], int firstValue, int lastValue);

void printArray(int numArray[], int length);
void swap(int* num1, int* num2);

void printArray(int numArray[], int length)
{
	int i;
	for(i=0;i<length;i++)
	{
		printf("%d ", numArray[i] );
	}
	printf("\r\n");
}

void swap(int* num1, int* num2)
{
	int temp;
	temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

void bubleSort(int numArray[], int length)
{
	int i, j, temp;

	for(i=0 ; i<length-1 ; i++)
	{
		for(j=0 ; i<length-(i-1) ; j++)
		{
			if(numArray[j] > numArray[j+1])
			{
				swap(&(numArray[j+1]), &(numArray[i]));
			}
		}
	}
}

void insertSort(int numArray[], int length)
{
	int i, j, refValue = 0;
	for(i=1 ; i<length; i++)
	{
		// If it is in order, it goes over.
		if(numArray[i-1] <= numArray[i])
			continue;

		for(j=0 ; j<i; j++)
		{
			refValue = numArray[i];

			// Find the case where the latter value is larger.
			if(numArray[j] > refValue)
			{
				//move data from index j to index j+1
				memcpy(&numArray[j+1], &numArray[j], sizeof(int) * (i-j));
				numArray[j] = refValue;
				break;
			}
		}
	}
}

void selectionSort(int numArray[], int length)
{
	int fillSlot, idx, maxPoint, temp;
	for(fillSlot=length-1; fillSlot>0 ; fillSlot--)
	{
		maxPoint = 0;
		for(idx=1; idx < fillSlot+1; idx++)
		{
			if(numArray[idx] > numArray[maxPoint])
			{
				maxPoint = idx;
			}
		}
		swap(&(numArray[fillSlot]), &(numArray[maxPoint]));
	}
}

void mergeSort(int numArray[], int length)
{
	
}

void quickSort(int numArray[], int length)
{
	quickSortStart(numArray, 0, length - 1);
}

void quickSortStart(int numArray[], int firstValue, int lastValue)
{
	int splitPoint;
	if(firstValue < lastValue)
	{
		splitPoint = quickSortFindSplit(numArray, firstValue, lastValue);
		quickSortStart(numArray, firstValue, splitPoint - 1);
		quickSortStart(numArray, splitPoint + 1 , lastValue);
	}
}


int quickSortFindSplit(int numArray[], int firstValue, int lastValue)
{
	int pivot = numArray[firstValue];
	int leftMark = firstValue + 1;
	int rightMark = lastValue;

	while(leftMark <= rightMark)
	{
		//Find a larger number than the pivot and increase leftMark. (from left to right)
		while((leftMark <= rightMark) && (numArray[leftMark] <= pivot))
		{
			leftMark += 1;
		}
		//Find a smaller number than the pivot and increase leftMark. (from right to left)
		while((rightMark >= leftMark) && (numArray[rightMark] >= pivot))
		{
			rightMark -= 1;
		}
		if(rightMark > leftMark)
		{
			swap(&(numArray[leftMark]), &(numArray[rightMark]));
		}
		else
		{
			break;
		}
	}

	swap(&(numArray[firstValue]), &(numArray[rightMark]));

	return rightMark;
}



int main()
{
	int numArray[] = {3,7,8,6,1,5,2,9,36,10};
	int length = sizeof(numArray)/sizeof(int);
	mergeSort (numArray, length);
	printArray(numArray, length);
	return 0;
}