C代写：CS251 Sorting

发表于   |   分类于

Introduction

工程编程中，Sorting通常都是出现在三方库中直接调用。Sorting的种类繁多，有下面几类：

插入排序

Straight Insertion Sort，直接插入排序
Shell’s Sort，希尔排序

选择排序

Simple Selection Sort，简单选择排序
Heap Sort，推排序

交换排序

Bubble Sort，冒泡排序
Quick Sort，快速排序

其他排序

Merge Sort，归并排序
Radix Sort，桶排序/基数排序

掌握以上几种基本排序算法的原理和实现，是每个工程师的基本功。刚开始的时候可以先研究其中一两个感兴趣的算法，自己动手画排序图，并编写简单代码来实现。
同时，可以使用一些三方算法库，来进行实际的编程操练。

Requirement

Implement void quicksort(unsigned int *a, int n) as a “C” style function in the file quicksort.cc

  1. The pivot should always be chosen as the first element of the array.
  2. See the given quicksort.cc file for how to determine running times. You can modify this file as you wish but I should be able to run it to get your output in the file specified.
  3. The main function in quicksort.cc reads from the file “quicksortinput” the n integers and writes the n integers to the file “quicksortoutput” in ascending sorted order. See “quicksortsampleinput” and “quicksortsampleoutput” for formatting details. Please make sure that your program can EXACTLY reproduce that output file given the input file. You may want to use the “diff” program to test this.
  4. The function sorts the array a of n positive integers with the quick sort algorithm.

Implement void radixsort(unsigned int *a, int n) as a “C” style function in the file radixsort.cc

  1. The elements of the array are positive and are represented with 32 bits.
  2. See the given radixsort.cc file for how to determine running times. You can modify this file as you wish but I should be able to run it to get your output in the file specified.
  3. The main function in radixsort.cc reads from the file “radixsortinput” the n integers and writes the n integers to the file “radixsortoutput” in ascending sorted order. See “radixsortsampleinput” and “radixsortsampleoutput” for formatting details. Please make sure that your program can EXACTLY reproduce that output file given the input file. You may want to use the “diff” program to test this.
  4. The function sorts the array a of n positive integers using the radix sort algorithm.

Analysis

需要实现Quicksort算法以及Radix sort算法。
本题难度不大，但需要理解和掌握这两种算法的原理和特点。
此外需要注意的是，测试集并非是结构化的数据，需要对测试集中字符进行分割，同时处理空行的问题。

Test

Input

1
2
3
4
5
    
23  1 1 1 1 1  232 32
        
39432 999999 1 111 11 2 2 2
4

Output

1
1 1 1 1 1 1 2 2 2 4 11 23 32 111 232 39432 999999