Mr.Linker ::

quickSort

프로그래밍 2008/03/27 20:37

import java.io.*;

public class Round02_Ex01 {

public static void swap(int[] num, int lhs, int rhs) {
int tmp = num[lhs];
num[lhs] = num[rhs];
num[rhs] = tmp;
}

public static void quickSort(int[] num, int l, int h) {

if (l < h) {
int m = partion(num, l, h);
quickSort(num, l, m - 1);
quickSort(num, m + 1, h);
}
}

public static int partion(int[] num, int l, int h) {

int firsthigh = l;
int p = h;

for (int i = 0; i < h; i++) {
if (num[i] < num[p]) {
swap(num, firsthigh, i);
firsthigh++;

}
}
swap(num, firsthigh, p);

return firsthigh;
}

public static void main(String[] ar) throws IOException {
int num[] = { 10, 20, 100, 50, 70 };

quickSort(num, 0, num.length - 1);

for (int i = 0; i < num.length; i++) {
System.out.println(num[i]);
}
}
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/21

#include <stdio.h>

#include <iostream>
#include <vector>

using namespace std;

void mergeSort(vector<int> arrayA, vector<int> arrayB, vector<int> &arrayRes)
{
int indexA=0, indexB=0;

while(indexA < arrayA.size() && indexB < arrayB.size()) {
if(arrayA[indexA] < arrayB[indexB]) {
arrayRes.push_back(arrayA[indexA]);
indexA++;
}
else {
arrayRes.push_back(arrayB[indexB]);
indexB++;
}
}
while(indexA < arrayA.size()) {
arrayRes.push_back(arrayA[indexA]);
indexA++;
}
while(indexB < arrayB.size()) {
arrayRes.push_back(arrayB[indexB]);
indexA++;
}

return;
}

int main()
{
int inputA[] = {1, 5, 37, 42, 61};
int inputB[] = {11, 15, 19, 48, 59};

vector<int> arrayA(&inputA[0], &inputA[sizeof(inputA)/sizeof(int)]);
vector<int> arrayB(&inputB[0], &inputB[sizeof(inputB)/sizeof(int)]);
vector<int> arrayRes;

mergeSort(arrayA, arrayB, arrayRes);

for(vector<int>::iterator vi=arrayA.begin(); vi != arrayA.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

for(vector<int>::iterator vi=arrayB.begin(); vi != arrayB.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

for(vector<int>::iterator vi=arrayRes.begin(); vi != arrayRes.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/14

Insertion Sort

프로그래밍 2007/11/18 13:31

#include <stdio.h>

#include <vector>
#include <iostream>

using namespace std;

void insertion_sort(vector<int> &array)
{
int i, j, cur_data, array_length = array.size();

//printf("array_length=>[%d]\n", array_length);
for(i=1; i<array_length; i++) {
cur_data = array[i];
for(j=i-1; j>=0 && (array[j] > cur_data); j--) {
array[j+1] = array[j];
}
array[j+1] = cur_data;
}

return;
}

int main()
{
int a[] = {26, 5, 37, 1, 61, 11, 59, 15, 48, 19};

vector<int> array(&a[0], &a[sizeof(a)/sizeof(int)]);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

insertion_sort(array);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/13

Selection Sort

프로그래밍 2007/11/18 13:29

#include <stdio.h>

#include <iostream>
#include <vector>

using namespace std;

void selectionSorter(vector<int> &array)
{
vector<int>::iterator imin;
int tmp;

for(vector<int>::iterator i=array.begin(); i!= array.end(); i++) {
imin = i;
for(vector<int>::iterator j=i; j!= array.end(); j++) {
if(*imin > *j) {
imin = j;
}
}
tmp = *i;
*i = *imin;
*imin = tmp;

/*
for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;
*/

}

return;
}

int main(void)
{
int input[] = {26, 5, 37, 1, 61, 11, 59, 15, 48, 19};
vector<int> array(&input[0], &input[sizeof(input)/sizeof(int)]);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

selectionSorter(array);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/12

infix를 postfix로 바꾸기 예제

프로그래밍 2007/11/12 23:50

한국정보올림피아드 강의 자료에 나와 있는 알고리즘을 따라서 코딩해 봤다..

1. 피연산자가 나오면 결과 배열에 차례로 담는다.
2. 연산자가 나오는 경우 스택에 집어넣는다. 스택에 넣기전에 스택 위에 위치한 자신보다 우선순위가 같거나 높은 연산자들을 pop시켜 결과 배열에 담는다.
3. 여는 괄호'('가 나오는 경우 스택에 집어넣는다.
4. 닫는 괄호')'가 나오는 경우 '('가 나올 때까지 stack에 담겨 있는 연산자를 pop시켜 결과 배열에 넣는다.

수식을 다 살펴본 후 스택에 담긴 연산자들을 모두 pop시켜 결과 배열에 넣는다.

#include <stdlib.h>

#include <iostream>
#include <vector>
#include <stack>
#include <list>
#include <string>

using namespace std;

#define printpos(func) cout << __FILE__ << ", " << func << ", " << __LINE__ << endl;

int getPriNum(char ch) {
if(ch == 'x') return 4;
else if(ch == '%') return 4;
else if(ch == '+') return 3;
else if(ch == '-') return 3;
else if(ch == '(') return 0;
else return 0;
}

int main(void)
{
const char *numForm="5+(4-2)-3x2";
list<char> infixList(&numForm[0], &numForm[strlen(numForm)]);

stack<char> opStack;
list<char> resList;

for(list<char>::iterator it=infixList.begin(); it!=infixList.end(); it++) {
//printf("%c:%d\n", *it, isdigit(*it));
if(isdigit(*it) != 0) {
resList.push_back(*it);
}
else {
if(*it == '(') {
opStack.push(*it);
}
else if(*it == ')') {
while(opStack.top() != '(') {
resList.push_back(opStack.top());
opStack.pop();
}
opStack.pop();
}
else {
if(opStack.empty() == 0) {
if(getPriNum(opStack.top()) >= getPriNum(*it)) {
//printf("%c, %c\n", opStack.top(), *it);
resList.push_back(opStack.top());
opStack.pop();
}
}
opStack.push(*it);
}
}

/*
printf("opStack.size()=>%d\n", opStack.size());
printf("=========\n");
stack<char> opTmpStack = opStack;
while(opTmpStack.empty() == 0) {
printf("%c\n", opTmpStack.top());
opTmpStack.pop();
}

printf("---------\n");

for(list<char>::iterator itRes=resList.begin(); itRes!=resList.end(); itRes++) {
printf("%c\n", *itRes);
}
printf("=========\n\n");
*/
}

/*
printf("opStack.size()=>%d\n", opStack.size());
printf("=========\n");
stack<char> opTmpStack = opStack;
while(opTmpStack.empty() == 0) {
printf("%c\n", opTmpStack.top());
opTmpStack.pop();
}
printf("---------\n");
*/

for(list<char>::iterator itRes=resList.begin(); itRes!=resList.end(); itRes++) {
printf("%c\n", *itRes);
}
//printf("=========\n\n");

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)