How to write data structure sorting lab report code
Introduce the necessary libraries and modules to define the sorting algorithm, test data generation, and performance evaluation functions, to implement the experiment logic, and to output the experiment results.
1, according to the experimental requirements, the introduction of sorting algorithm implementation code or libraries for generating test data.
2. Implement different sorting algorithms, such as bubble sort, insertion sort, selection sort, quick sort, etc. Ensure that each sorting algorithm has clear inputs and outputs, and write functions to generate test data according to the experimental requirements.
Summary and Comparison of Various Sorting Algorithms
Sorting algorithms are one of the most basic algorithms in Data Structures and Algorithms.
Sorting algorithms can be categorized into internal and external sorting, internal sorting is where the data records are sorted in memory, while external sorting is where access to external memory is required during the sorting process due to the large size of the data to be sorted, which can’t hold all the sorted records at once. Common internal sorting algorithms are: Insertion Sort, Hill Sort, Selection Sort, Bubble Sort, Normalization Sort, Quick Sort, Heap Sort, Base Sort, and so on. Summarized in a diagram:
Click on the following image for a larger view:
About Time Complexity
Square Order (O(n2)) SortThe various types of simple sorts: direct insertion, direct selection, and bubble sort.
Linear logarithmic order (O(nlog2n)) sort quick sort, heap sort, and subsumption sort;
O(n1+§)) sort, where § is a constant between 0 and 1. Hill sort
Linear order (O(n)) sort base sort, in addition to bucket and box sorts.
On stability
Stable sorting algorithms: bubble sort, insertion sort, subsumption sort, and base sort.
Sorting algorithms that are not stable: selection sort, quick sort, Hill sort, and heap sort.
Nomenclature:
n: size of data k: number of “buckets” In-place: occupies constant memory, no extra memory Out-place: occupies extra memory Stability: the order of 2 equal key values after sorting is the same as their order before sorting
Contains the following:
1, Bubble Sort2, Selection Sort3, Insertion Sort4. Hill Sort5, Subsumption Sort6, Quick Sort7, Heap Sort8, Counting Sort9, Bucket Sort10, Base Sort
Sorting algorithms include the following:
Bubble Sort Algorithm
Bubble Sort (BubbleSort) is also a simple and intuitive sorting algorithm. It repeatedly walks through the array to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The walk through the array is repeated until no more swaps are needed, meaning that the array has been sorted. The algorithm gets its name from the fact that the smaller elements are slowly “floated” to the top of the array by swapping.
Selective sorting algorithm
Selective sorting is a simple and intuitive sorting algorithm that has O(n?) time complexity no matter what data goes into it. So when it is used, the smaller the data size, the better. The only benefit might be that it doesn’t take up extra memory space.
Insertion Sort Algorithm
The code implementation of insertion sort is not as simple and brutal as bubble sort and selection sort, but its principle should be the easiest to understand, because anyone who has ever played poker should be able to understand it in seconds. Insertion sort is one of the simplest and most intuitive sorting algorithms, and it works by constructing an ordered sequence of unsorted data, scanning backward and forward through the sorted sequence, finding the appropriate position and inserting it.
Hill Sort Algorithm
Hill Sort, also known as Decreasing Incremental Sort, is a more efficient and improved version of Insertion Sort. However, Hill Sort is a non-stable sorting algorithm.
Merge Sort Algorithm
Mergesort is an efficient sorting algorithm built on the operation of merging. The algorithm is a very typical application using DivideandConquer.
Fast Sort Algorithm
Fast sort is a sorting algorithm developed by Tony Hall. In the average case, it takes Ο(nlogn) comparisons to sort n items. In the worst case it takes Ο(n2) comparisons, but this is not common. In fact, quick sort is often significantly faster than other Ο(nlogn) algorithms because its innerloop can be implemented efficiently on most architectures.
Heap Sort Algorithm
Heapsort refers to a sorting algorithm designed to take advantage of the data structure known as a heap. A heap is a structure that approximates a complete binary tree and simultaneously satisfies the properties of a heap: i.e., the key value or index of a child node is always less than (or greater than) its parent. Heap sort can be described as a selection sort that utilizes the concept of a heap to sort.
Counting Sort Algorithm
The heart of counting sort lies in the conversion of input data values into keys stored in an additional open array space. As a linear time complexity sort, counting sort requires that the input data be integers with a defined range.
Bucket Sort Algorithm
Bucket sort is an upgraded version of counting sort. It utilizes a mapping of functions, and the key to efficiency lies in the determination of this mapping function.
Base Sort Algorithm
Base Sort is a non-comparative integer sort algorithm, which works by cutting the integer into different numbers by digits, and then comparing each digit separately. Since integers can also express strings (such as names or dates) and floating-point numbers in a particular format, base sort is not exclusive to integers.