반응형
정렬 알고리즘이란
잘 찾기 위해 하는 정리.
탐색을 위한 정렬.
데이터를 빠르고 쉽게 찾을 수 있게 하는 목적.
버블 정렬
데이터를 정렬하는 과정이 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습이라 붙여진 명칭
집합 내의 이웃 되는 데이터를 순회하면서 비교 및 교환으로 정렬을 수행
사용을 지양해야 하는 정렬 알고리즘.
O(n^2)
삽입 정렬
뒤죽박죽 되어있는 트럼프 카드를 순서대로 정리하는 모습
데이터를 순회 하면서 필요한 값을 뽑아내어 필요한 위치에 삽입하여 정렬을 수행
사용을 지양해야 하는 정렬 알고리즘
O(n^2)
퀵 정렬
빨라서 이름이 퀵인 정렬
분할 정복을 기반한 알고리즘 : 적군를 싸우기 보다는 잘게 나누어 싸우는 전법
기준 값의 왼쪽에는 작은 수들을 놓고 오른쪽은 큰 수들 배치하여 정렬을 수행
사용을 지향해야 하는 정렬 알고리즘
O(nlogn)
C소스
버블 정렬
/*
* BubbleSort.c
*
* Created on: 2019. 1. 4.
* Author: otrodevym
*/
#include <stdio.h>
#include <stdlib.h>
void BubbleSort(int DataSet[], int Length){
int i = 0;
int j = 0;
int temp = 0;
for(i = 0; i < Length; i++){
for(j = 0; j < Length-(i+1); j++){
if(DataSet[j] > DataSet[j+1]){
temp = DataSet[j+1];
DataSet[j+1] = DataSet[j];
DataSet[j] = temp;
}
}
}
}
int BubbleSortMain(){
int DataSet[] = {6, 4, 2, 3, 1, 5};
int Length = sizeof(DataSet) / sizeof(DataSet[0]);
int i = 0;
BubbleSort(DataSet, Length);
for(i = 0; i < Length; i++){
printf(" %d " , DataSet[i]);
}
printf("\n");
return 0;
}
삽입 정렬
/*
* InsertSort.c
*
* Created on: 2019. 1. 4.
* Author: otrodevym
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void InsertionSort(int DataSet[], int Length){
int i = 0;
int j = 0;
int value = 0;
for(i = 1; i < Length; i++){
if(DataSet[i-1] <= DataSet[i]){
continue;
}
value = DataSet[i];
for(j = 0; j < i; j++){
if(DataSet[j] > value){
memmove(&DataSet[j+1], &DataSet[j], sizeof(DataSet[0])*(i-j));
DataSet[j] = value;
break;
}
}
}
}
int InsertionSortMain(){
int DataSet[] = {6, 4, 2, 3, 1, 5};
int Length = sizeof(DataSet) / sizeof(DataSet[0]);
int i = 0;
InsertionSort(DataSet, Length);
for(i = 0 ; i < Length; i++){
printf("%d " , DataSet[i]);
}
printf("\n");
return 0;
}
퀵 정렬
/*
* QuickSort.c
*
* Created on: 2019. 1. 4.
* Author: otrodevym
*/
#include <stdio.h>
void Swap(int* A, int* B){
int temp = *A;
*A = *B;
*B = temp;
}
int Partition(int DataSet[], int Left, int Right){
int First = Left;
int Pivot = DataSet[First];
++Left;
while(Left <= Right){
while(DataSet[Left] <= Pivot && Left < Right){
++Left;
}
while(DataSet[Right] > Pivot && Left <= Right){
--Right;
}
if(Left < Right){
Swap(&DataSet[Left], &DataSet[Right]);
}else{
break;
}
}
Swap(&DataSet[First], &DataSet[Right]);
return Right;
}
void QuickSort(int DataSet[], int Left, int Right){
if(Left < Right){
int Index = Partition(DataSet, Left, Right);
QuickSort(DataSet, Left, Index-1);
QuickSort(DataSet, Index+1, Right);
}
}
int QuickSortMain(){
int DataSet[] = {6, 4, 2, 3, 1, 5};
int Length = sizeof(DataSet)/sizeof(DataSet[0]);
int i = 0;
QuickSort(DataSet, 0, Length-1);
for(i = 0; i < Length; i++){
printf("%d ", DataSet[i]);
}
printf("\n ");
return 0;
}
퀵정렬2
/*
* QuickSort2.c
*
* Created on: 2019. 1. 4.
* Author: otrodevym
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int CompareScore(const void *_eleml1, const void *_elem2){
int* elem1 = (int*)_eleml1;
int* elem2 = (int*)_elem2;
if(*elem1 > *elem2){
return 1;
}else if(*elem1 < *elem2){
return -1;
}else{
return 0;
}
}
int main(){
int DataSet[] = {6, 4, 2, 3, 1, 5};
int Length = sizeof(DataSet)/sizeof(DataSet[0]);
int i = 0;
qsort((void*)DataSet, Length, sizeof(int), CompareScore);
for(i = 0; i < Length; i++){
printf("%d ", DataSet[i]);
}
printf("\n");
return 0;
}
Java 소스
버블 정렬
package e_sort;
public class BubbleSort {
private void BubbleSort(int[] data) {
int temp = 0;
for(int i = 0; i < data.length; i++) {
for(int j = (i+1); j < data.length; j++) {
if(data[i] > data[j]) {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
}
}
public static void main(String args[]) {
BubbleSort bs = new BubbleSort();
int[] data = {5, 2, 4, 3, 1,};
bs.BubbleSort(data);
for(int i : data) {
System.out.print(i + " " );
}
}
}
삽입 정렬
package e_sort;
public class InsertionSort {
public void InsertionSort(int[] data) {
int temp = 0;
for (int i = 1; i < data.length; i++) {
temp = data[i];
int j = i-1;
while(j >=0 && temp < data[j]) {
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
public static void main(String args[]) {
InsertionSort is = new InsertionSort();
int[] data = { 5, 2, 3, 4, 1 };
is.InsertionSort(data);
for (int i : data) {
System.out.print(" " + i);
}
}
}
퀵 정렬
package e_sort;
public class QuickSort {
public void swap(int[] data, int index1, int index2) {
int temp = 0;
temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
}
public int partition(int[] data, int left, int right) {
int first = left;
int pivot = data[left];
while(left < right) {
while(data[left] <= pivot && left < right) {
++left;
}
while(data[right] > pivot && left <= right) {
--right;
}
if(left < right) {
swap(data, left, right);
}else {
break;
}
}
swap(data, first, right);
return right;
}
public void quickSort(int[] data, int left, int right) {
if(left < right) {
int index = partition(data, left, right);
quickSort(data, left, index-1);
quickSort(data, index+1, right);
}
}
public static void main(String args[]) {
QuickSort qs = new QuickSort();
int data[] = {6, 4, 2, 3, 1, 5};
qs.quickSort(data, 0, data.length-1);
for(int i : data) {
System.out.print(i + " ");
}
}
}
반응형
'개발(합니다) > 컴퓨터 일반&CS' 카테고리의 다른 글
| [알고리즘]우선순위 큐와 힙 (0) | 2019.01.07 |
|---|---|
| [알고리즘]탐색/검색(순차, 자기 구성, 이진 탐색, 레드블랙트리) (0) | 2019.01.05 |
| [자료구조]트리(Tree) (0) | 2019.01.03 |
| [자료구조]큐(Queue) (0) | 2019.01.02 |
| [자료구조]스택(Stack) (0) | 2018.12.31 |
