직접 코드 구현한거라 가독성 및 최적화는 안좋을수 있습니다. 참고하시고 봐주시면 감사하겠습니다.
1.선택정렬
시간 복잡도 :
Best : n^2
Avg : n^2
Worst : n^2
정수 6만개 기준 Run-time (단위: sec) : 10.842
코드구현
더보기
int[] arr;
arr = new int[6] { 5, 2, 4, 6, 1, 3 };
for (int i = 0; i < arr.Length; i++)
{
for(int j = i+1; j< arr.Length;j++)
{
//오름차순 정렬
if (arr[i] > arr[j])
{
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
}
foreach (int num in arr)
{
Console.Write(num + " ");
};
Console.WriteLine();2.삽입정렬
시간 복잡도 :
Best : n (데이터들이 정렬이 되있다는 가정하에)
Avg : n^2
Worst : n^2
정수 6만개 기준 Run-time (단위: sec) : 7.438
코드구현
더보기
int[] arr;
arr = new int[6] { 5, 2, 4, 6, 1, 3 };
for (int i = 1 ; i < arr.Length; i++)
{
int key = arr[i];
int keyIndex = i;
for(int j = i-1; j >= 0; j--)
{
if(key < arr[j])
{
int tmp = arr[j];
arr[j] = key;
arr[keyIndex] = tmp;
}
keyIndex--;
}
}
foreach (int num in arr)
{
Console.Write(num + " ");
};
Console.WriteLine();3.퀵정렬
시간 복잡도 :
Best : n log n
Avg : n log n
Worst : n^2
정수 6만개 기준 Run-time (단위: sec) : 0.014
코드구현
더보기
public static int[] Swap(int[] arr,int index1,int index2)
{
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
return arr;
}
public static int[] QuickSort(int[] arr, int left, int right)
{
if(left >= right)
{
return arr;
}
int pivot = left;
int low = pivot + 1;
int high = right;
bool isLow = false;
bool isHigh = false;
while (low <= high)
{
if (arr[pivot] < arr[low])
{
isLow = true;
}
else
{
low++;
}
if (arr[pivot] > arr[high])
{
isHigh = true;
}
else
{
high--;
}
if (isLow && isHigh)
{
arr = Swap(arr, low, high);
isLow = false;
isHigh = false;
}
}
arr = Swap(arr, pivot, high);
pivot = high; // pivot 기준으로 좌 우로 나눳기에 pivot 인덱스를 high으로 변경해줘야 정상적으로 동작함
arr = QuickSort(arr, left, pivot-1);
arr = QuickSort(arr, pivot+1, right);
return arr;
}
public static int[] Partition(int[] arr,int pivot, int left , int right)//분할
{
return arr = QuickSort(arr, left, right);
}
static void Main(string[] args)
{
int[] arr;
//퀵정렬은 분할 정복 방법을 사용 / 과정은 분할 -> 정복 -> 결합 이다.
//분할 : pivot을 기준으로 작은건 왼쪽 큰건 오른쪽으로 배치
//정복 : pivot 기준으로 나눠진 배열을 정렬, 더 분할 할수 있으면 분할
//결합 : 더이상 분할 할수가 없으면 정렬된 부분배열들 하나으 배열로 결합
//arr = new int[6] { 5, 2, 4, 6, 1, 3 };
arr = new int[9] { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
arr = Partition(arr,0, 0, arr.Length -1);
foreach (int num in arr)
{
Console.Write(num + " ");
};
Console.WriteLine();
}4.병합정렬
시간 복잡도 :
Best : n log n
Avg : n log n
Worst : n log n
정수 6만개 기준 Run-time (단위: sec) : 0.026
코드구현
더보기
public static int[] Swap(int[] arr,int index1,int index2)
{
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
return arr;
}
public static int[] Merge(int[]arr , int left, int mid ,int right)
{
int[] temp = new int [arr.Length]; // Merge할 새 배열 만들기
//실제로 배열을 분할한건 아니고 index로 범위를 만들어 분할하게 가정
int Index1 = left; //분할한 arr1의 인덱스
int Index1Max = mid; //분할한 arr1의 범위
int Index2 = mid+1; //분할한 arr2의 인덱스
int Index2Max = right; //분할한 arr2의 범위
int tempIndex = left; //위치할 arr index 위치
while (Index1 <= Index1Max && Index2 <= Index2Max)
{
if (arr[Index1] > arr[Index2])
{
temp[tempIndex] = arr[Index2];
tempIndex++;
Index2++;
}
else
{
temp[tempIndex] = arr[Index1];
tempIndex++;
Index1++;
}
}
for(int i = Index1; i<= Index1Max ; i++)
{
temp[tempIndex] = arr[i];
tempIndex++;
}
for (int i = Index2; i <= Index2Max; i++)
{
temp[tempIndex] = arr[i];
tempIndex++;
}
for (int i = left; i <= right ; i++)
{
arr[i] = temp[i];
}
return arr;
}
public static int[] MergeSort(int[]arr, int left ,int right)
{
if(left >= right)
{
return arr;
}
int mid = (left + right) / 2;
arr = MergeSort(arr, left, mid);
arr = MergeSort(arr, mid + 1, right);
arr = Merge(arr, left,mid, right);
return arr;
}
public static int[] PartitionMerge(int[] arr, int left ,int right)
{
int mid = (left+right)/2;
arr = MergeSort(arr, left, mid);
arr = MergeSort(arr, mid+1, right);
arr = Merge(arr, left, mid, right);
return arr;
}
static void Main(string[] args)
{
int[] arr;
//병합 정렬도 퀵정렬과 마찬가지로 분할 정복 방법을 이용한 정렬이다.
arr = new int[8] { 21, 10, 12, 20, 25, 13, 15, 22 };
arr = PartitionMerge(arr,0,arr.Length-1);
foreach (int num in arr)
{
Console.Write(num + " ");
};
Console.WriteLine();
}