Time and Space Complexity of Selection Sort on Linked List

In this article, we will learn about the space and time complexity of the Merge sort algorithm on Linked List using Mathematical analysis of various cases.

Table of Contents

1. Time Complexity Analysis of Selection Sort on Linked List
2. Worst Case Time Complexity Analysis
3. Best Case Time Complexity Analysis
4. Average Case Time Complexity Analysis
5. Space Complexity Analysis
6. Comparison between Selection Sort on Array and Linked list
7. Summarization

C++ implementation of Selection Sort on Linked List

Code:

#include<bits/stdc++.h>
using namespace std;

// Class to define Node
class Node {
	public:
		int data;
		Node* next;
	
		Node(int data) {
			this->data = data;
			next = NULL;
		}
};

//Function to implement Selection sort 
void selectionSort(Node* head) {
    
    Node* thead = head;
    
    //Traverse all over the List
    while(thead) {
        
        Node* min  = thead;
        Node* temp = thead->next;
        
        //Find the smallest element in  the remaining List.
        while(temp) {
            
        	if(min->data > temp->data) {
        		min = temp; 
        	}
        	temp = temp->next;
        }
        
        //Swapping Smallest
        int t = thead->data;
        thead->data = min->data;
        min->data = t;

    	thead = thead->next;
    }
}

int main() {
    
    //Linked List : 3 1 2 11 9 6
	Node* head = new Node(3);
	Node* temp = head;
	temp->next = new Node(1);
	temp = temp->next;
	temp->next = new Node(2);
	temp = temp->next;
	temp->next = new Node(11);
	temp = temp->next;
	temp->next = new Node(9);
	temp = temp->next;
	temp->next = new Node(6);
	temp = temp->next;

	selectionSort(head);

    //Output
	while(head) {
		cout<<head->data<<' ';
		head = head->next;
	}
	cout<<endl;

	return 0;
}

Output:

Sorted Linked List : 1 2 3 6 9 11

Time Complexity Analysis of Selection Sort on Linked List

Let the Size of unsorted Linkedlist be n.

    unsorted Linkedlist: 3 1 2 5 4 6
   
    Step 1:    | 3 1 2 5 4 6   0 -> N
    Step 2:    1 | 3 2 5 4 6   1 -> N-1
    Step 3:    1 2 | 3 5 4 6   2 -> N-2
    Step 4:    1 2 3 | 5 4 6      .
    Step 5:    1 2 3 4 | 7 6      .
    Step 6:    1 2 3 4 6 | 7      1

Step 1: There is no sorted element. To make the first element sorted we traverse the whole LinkedList of size N.
Step 2: For sorting the second element we travel the Linkedlist of size N-2.
Step 3: For sorting the third element we travel the Linkedlist of size N-3.
....
Step N-1: For sorting the (N-1)th element we travel the Linkedlist of size 1.
Step N: The last element is already sorted.

Time taken to sort n elements i.e.
T(n) = k(n) + k(n-1) + k(n-2) + ... + k(2) + k(1) , where k is constant which means some constant work is done while processing every step.
T(n) = k{n + (n-1) + (n-2) + ... + 2 + 1}
T(n) = kn(n-1) / 2;
T(n) = kn^2/2 - kn/2
Hence total time complexity : θ(n^2)

Worst Case Time Complexity Analysis

Worst Time Complexity occur when the Linkedlist is completely unsorted(or sorted in descending order).
E.g: 5 4 3 2 1
For every smallest node it has to travel to the extreme. The complexity remains the same.
Hence, Worst Case Time Complexity : O(n^2)

Best Case Time Complexity Analysis

Worst Time Complexity occur when the Linkedlist is already sorted(or sorted in increasing order).
E.g: 1 2 3 4 5
Yet the List is already sorted, it will search for the smallest element in the same manner explained. So, it's complexity will not change.
Hence, Best Case Time Complexity : Ω(n^2)

Average Case Time Complexity Analysis

It's the case when the Linkedlist list is neither in increasing order or decreasing order i.e all the elements are jumbled.
E.g: 5 1 3 4 2
And the no. operations to find the elements remains same. So, there is no change in it's complexity.
Hence, Average Case Time Complexity : θ(n^2)

Space Complexity Analysis

Space Complexity: O(1) i.e constant space.
As it doesn't require any extra space to sort the List. It itself sort the List in the given Linkedlist.

Comparison between Selection Sort on Array and Linked list

The time complexity of Selection Sort is same on both Array and Linked List as:

• The major disadvantage of Linked List over array is lack of random access.
• This limitation does not play any role as Selection Sort involves only sequential access.

In practice, Selection sort performs better on Array compared to Linked List as:

• In array, data is stored sequentially in memory while in case of Linked List, it is scattered.
• When a memory access is made, adjacency memory is placed in the cache and hence, the second memory access of an adjancent element is instant
• Due to this, Array is Cache friendly and results in better performance despite having the same Time Complexity.

Summarization:

Thank You!