数据结构之——排序

Created in December 12, 2015

2015   ·   datastructure

                                Sorting Algorithm

  • Sorting Algorithm

Introduction: A sorting algorithm is an algorithm that puts elements of a list in a certain order.

screenshot

There are some sorting algorithms above.I’m gonna implement some of them in this tutorial then.

And the complexity of this algorithm are:

screenshot

  • The Bubble Sort is the simplest sorting algorithm that works by repeatedly swaping the adjacent elements if they are in wrong order.

 

  •  In Order To get the exact time of this algorithm to show the difference ,using the to calculate the time of implementing.

 

Example:<Comes From GeeksforGeeks.org> First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 ) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

And the following implementation of Bubble Sort is:

#include <iostream>
#include <time.h>
using namespace std;

void swap(int *a, int *b){
	int c;
	c = *a;
	*a = *b;
	*b = c;
}
void BubbleSort(int arr[], int n){
	for (int i = 0; i < n - 1; i++)
	for (int j = 0; j < n - i - 1; j++){
		if (arr[j] > arr[j + 1])
			swap(&arr[j], &arr[j + 1]);
	}

}
// Driver program to test above functions
int main()
{
	long beginTime = clock();//获得开始时间，单位为毫秒
	int arr[] = { 64, 34, 25, 12, 22, 11, 90, 20, 87, 893, 498, 492, 4982, 0, 4984, 4982, -1, 4920, 3742, 1, 30, 173, 1983, 3091, 17463, 70, 21683, 13001, 26335, 32326, 266, 12807, 30369, 22480, 17985, 10274, 4438, 9699, 16814, 17445, 21674, 20239, 16626, 22849, 21211, 14634, 31962, 15904, 17597, 17221, 31619, 13943, 7426, 7134, 24002, 6875, 24760, 18264, 7106, 13013, 26899, 27304, 29935, 30008, 29293, 11856, 5907, 8882, 7307, 19857, 16575, 28322, 16418, 9692, 25325, 10793, 15769, 23179, 1507, 9604, 10513, 24782, 30043, 15257, 30627, 2024, 30688, 15311, 4584, 20891, 5499, 9763, 28607, 12000, 12687, 28025, 8522, 29916, 31746, 13359, 26938, 7696, 32157, 14072, 19533, 11216, 17334, 23016, 14868, 15350, 28428, 3019, 13050, 9943, 10738, 29627, 3970, 14710, 18864, 7410, 19664, 24568, 7974, 5340};
	int n = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, n);
	printf("Sorted array: n");
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
	long endTime = clock();//获得结束时间
	//cout << "===========================" << endl;
	cout << "beginTime:" << beginTime << endl
		<< "endTime:" << endTime << endl
		<< "endTime-beginTime:" << endTime - beginTime << endl;
	system("pause");
}

The Result is:

screenshot

  • Selection Sort

The Selection Sort algorithm sorts an array by repeatedly finding the minimum element form unsorted part and putting it at the beginning.

FOR EXAMPLE:

arr[] = 64 25 12 22 11 // Find the minimum element in arr[0…4] and pla// ce it at beginning 11 25 12 22 64 // Find the minimum element in arr[1…4] and // place it at beginning of arr[1…4] 11 12 25 22 64 // Find the minimum element in arr[2…4] and // place it at beginning of arr[2…4] 11 12 22 25 64 // Find the minimum element in arr[3…4] and // place it at beginning of arr[3…4] 11 12 22 25 64 The Following Implementation Is:

#include <iostream>
#include <time.h>
using namespace std;

void swap(int *a, int *b){
	int c;
	c = *a;
	*a = *b;
	*b = c;
}
void SelectionSort(int arr[], int n){
	int i,j,min_key = 0;
	for (i = 0; i < n - 1; i++)
	{
		min_key = i;
		for (j = i + 1; j < n; j++)
			if (arr[j] < arr[min_key])
				min_key = j;
			swap(&arr[min_key], &arr[i]);
	}
}
// Driver program to test above functions
int main()
{
	long beginTime = clock();//获得开始时间，单位为毫秒
	int arr[] = { 64, 34, 25, 12, 22, 11, 90, 20, 87, 893, 498, 492, 4982, 0, 4984, 4982, -1, 4920, 3742, 1, 30, 173, 1983, 3091, 17463, 70, 21683, 13001, 26335, 32326, 266, 12807, 30369, 22480, 17985, 10274, 4438, 9699, 16814, 17445, 21674, 20239, 16626, 22849, 21211, 14634, 31962, 15904, 17597, 17221, 31619, 13943, 7426, 7134, 24002, 6875, 24760, 18264, 7106, 13013, 26899, 27304, 29935, 30008, 29293, 11856, 5907, 8882, 7307, 19857, 16575, 28322, 16418, 9692, 25325, 10793, 15769, 23179, 1507, 9604, 10513, 24782, 30043, 15257, 30627, 2024, 30688, 15311, 4584, 20891, 5499, 9763, 28607, 12000, 12687, 28025, 8522, 29916, 31746, 13359, 26938, 7696, 32157, 14072, 19533, 11216, 17334, 23016, 14868, 15350, 28428, 3019, 13050, 9943, 10738, 29627, 3970, 14710, 18864, 7410, 19664, 24568, 7974, 5340 };
	int n = sizeof(arr) / sizeof(arr[0]);
	SelectionSort(arr, n);
	printf("Sorted array: n");
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
	long endTime = clock();//获得结束时间
	//cout << "===========================" << endl;
	cout << "beginTime:" << beginTime << endl
		<< "endTime:" << endTime << endl
		<< "endTime-beginTime:" << endTime - beginTime << endl;
	system("pause");
}

And The Result:

screenshot

 

  • Quick Sort

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. 1) Always pick first element as pivot. 2) Always pick last element as pivot (implemented below) 3) Pick a random element as pivot. 4) Pick median as pivot.

  • The following implementation is: ```c++ #include #include using namespace std;

void swap(int *a, int *b){ int c; c = *a; *a = *b; *b = c; }

int partition(int arr[], int l, int h) { int x = arr[h]; int i = l - 1; for (int j = l; j <= h - 1; j++) if (arr[j] <= x){ i++; swap(&arr[j], &arr[i]); } swap(&arr[i+1],&arr[h]); return (i + 1); }

void QuickSort(int arr[], int l,int h){ if (l < h){ int p = partition(arr, l, h); QuickSort(arr, l, p - 1); QuickSort(arr, p + 1, h); } } // Driver program to test above functions int main() { long beginTime = clock();//获得开始时间，单位为毫秒 int arr[] = { 64, 34, 25, 12, 22, 11, 90, 20, 87, 893, 498, 492, 4982, 0, 4984, 4982, -1, 4920, 3742, 1, 30, 173, 1983, 3091, 17463, 70, 21683, 13001, 26335, 32326, 266, 12807, 30369, 22480, 17985, 10274, 4438, 9699, 16814, 17445, 21674, 20239, 16626, 22849, 21211, 14634, 31962, 15904, 17597, 17221, 31619, 13943, 7426, 7134, 24002, 6875, 24760, 18264, 7106, 13013, 26899, 27304, 29935, 30008, 29293, 11856, 5907, 8882, 7307, 19857, 16575, 28322, 16418, 9692, 25325, 10793, 15769, 23179, 1507, 9604, 10513, 24782, 30043, 15257, 30627, 2024, 30688, 15311, 4584, 20891, 5499, 9763, 28607, 12000, 12687, 28025, 8522, 29916, 31746, 13359, 26938, 7696, 32157, 14072, 19533, 11216, 17334, 23016, 14868, 15350, 28428, 3019, 13050, 9943, 10738, 29627, 3970, 14710, 18864, 7410, 19664, 24568, 7974, 5340 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0,n-1); printf(“Sorted array: n”); for (int i = 0; i < n; i++) cout « arr[i] « ” “; cout « endl; long endTime = clock();//获得结束时间 //cout « ”===========================” « endl; cout « “beginTime:” « beginTime « endl « “endTime:” « endTime « endl « “endTime-beginTime:” « endTime - beginTime « “ms”«endl; system(“pause”); }

And the Result :

<p align="center">
  <img src="https://zhengliangliang.files.wordpress.com/2015/12/2015-12-12_212325.png" alt="screenshot" width="80%" height="auto">
</p>

- **Merge Sort**

**MergeSort is a [Divide and Conquer](http://www.geeksforgeeks.org/divide-and-conquer-set-1-find-closest-pair-of-points/) algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merg() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details.**

Example:

**MergeSort(arr[], l,  r)**
If r > l
     **1.** Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
    **2.** Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     **3.** Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     **4.** Merge the two halves sorted in step 2 and        3:
             Call merge(arr, l, m, r)

 <p align="center">
  <img src="https://zhengliangliang.files.wordpress.com/2015/12/2015-12-12_215635.png" alt="screenshot" width="80%" height="auto">
</p>

The Complexity Of The Merge Sort:

This [Link](https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort)

- **Insertion Sort**

**Algorithm** // Sort an arr[] of size n insertionSort(arr, n) Loop from i = 1 to n-1. ……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

**Example:** **12**, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 5 (Size of input array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12 **11, 12**, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13 **11, 12, 13**, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position. **5, 11, 12, 13**, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position. **5, 6, 11, 12, 13**

- The following implementation:
```c++
#include <iostream>
#include <time.h>
using namespace std;

void InsertionSort(int arr[], int n){
	int key,j;
	for (int i = 1; i < n; i++){
		key = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j]>key){
			arr[j + 1] = arr[j];
			j = j - 1;
		}
		arr[j + 1] = key;//前面被覆盖的要补回来
	}
}

// Driver program to test above functions
int main()
{
	long beginTime = clock();//获得开始时间，单位为毫秒
	int arr[] = { 64, 34, 25, 12, 22, 11, 90, 20, 87, 893, 498, 492, 4982, 0, 4984, 4982, -1, 4920, 3742, 1, 30, 173, 1983, 3091, 17463, 70, 21683, 13001, 26335, 32326, 266, 12807, 30369, 22480, 17985, 10274, 4438, 9699, 16814, 17445, 21674, 20239, 16626, 22849, 21211, 14634, 31962, 15904, 17597, 17221, 31619, 13943, 7426, 7134, 24002, 6875, 24760, 18264, 7106, 13013, 26899, 27304, 29935, 30008, 29293, 11856, 5907, 8882, 7307, 19857, 16575, 28322, 16418, 9692, 25325, 10793, 15769, 23179, 1507, 9604, 10513, 24782, 30043, 15257, 30627, 2024, 30688, 15311, 4584, 20891, 5499, 9763, 28607, 12000, 12687, 28025, 8522, 29916, 31746, 13359, 26938, 7696, 32157, 14072, 19533, 11216, 17334, 23016, 14868, 15350, 28428, 3019, 13050, 9943, 10738, 29627, 3970, 14710, 18864, 7410, 19664, 24568, 7974, 5340 };
	int n = sizeof(arr) / sizeof(arr[0]);
	InsertionSort(arr,n);
	printf("Sorted array: n");
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
	long endTime = clock();//获得结束时间
	//cout << "===========================" << endl;
	cout << "beginTime:" << beginTime << endl
		<< "endTime:" << endTime << endl
		<< "endTime-beginTime:" << endTime - beginTime << "ms" << endl;
	system("pause");
}

And The Result

screenshot

  • ShellSort

ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow exchange of far items. In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.



    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • What is Mathematics: Solution Chapter 3
  • What is Mathematics: Solution Chapter 2
  • What is Mathematics: Solution Chapter 1
  • A small guide to supplements: What you need to know
  • 混乱与秩序