Back to Course

Data Structures and Algorithms with C++

0% Complete
0/0 Steps
  1. Introduction to Data Structures and Algorithms
    Overview of Data Structures and Algorithms with C++
  2. Importance of Data Structures and Algorithms in Programming with C++
  3. How to Choose the Right Data Structure or Algorithm for a given Problem with C++
  4. Basic C++ Concepts Review
    Variables and Data Types in C++
  5. Control Flow Statements in C++
  6. Classes and Objects in C++
  7. Methods and Constructors in C++
  8. Basic Input and Output in C++
  9. Data Structures
    Arrays in C++
  10. Stacks and Queues in C++
  11. Linked Lists in C++
  12. Hash Tables in C++
  13. Trees in C++
  14. Types of Trees
    Binary Search Trees in C++
  15. Cartesian Trees in C++
  16. B-Trees in C++
  17. Red-Black Trees in C++
  18. Splay Trees in C++
  19. AVL Trees in C++
  20. KD Trees in C++
  21. Min Heap in C++
  22. Max Heap in C++
  23. Trie Trees in C++
  24. Suffix Trees in C++
  25. Sorting Algorithms
    Quicksort in C++
  26. Mergesort in C++
  27. Timsort in C++
  28. Heapsort in C++
  29. Bubble Sort in C++
  30. Insertion Sort in C++
  31. Selection Sort in C++
  32. Tree Sort in C++
  33. Shell Sort in C++
  34. Bucket Sort in C++
  35. Radix Sort in C++
  36. Counting Sort in C++
  37. Cubesort in C++
  38. Searching Algorithms
    Linear Search in C++
  39. Binary Search in C++
  40. Graphing Algorithms
    Breadth First Search (BFS) in C++
  41. Depth First Search (DFS) in C++
  42. Dijkstra’s Algorithm in C++
  43. Algorithm Design Techniques
    Greedy Algorithms in C++
  44. Dynamic Programming in C++
  45. Divide and Conquer in C++
  46. Backtracking in C++
  47. Randomized Algorithms in C++
  48. Conclusion
    Recap of DSA with C++

Participants 676

Show more

Selection Sort is a sorting algorithm that is used to arrange elements of an array in a specific order. It is one of the most basic sorting algorithms and is often taught in courses on Data Structures and Algorithms with C++. In this article, we will discuss the Selection Sort algorithm, its time complexity, and its space complexity. We will also provide code examples to illustrate the Selection Sort algorithm in action.

What is Selection Sort?

Selection Sort is an in-place comparison sorting algorithm that runs in O(n²) time and can be used to sort elements in an array or a list. It works by selecting the smallest element in the array and swapping it with the first element. Then, it selects the second-smallest element and swaps it with the second element. This process continues until the array is sorted in ascending order.

Selection Sort in C++

Now let’s look at an example of Selection Sort in C++. The following code shows a basic implementation of the Selection Sort algorithm.

#include <iostream>
using namespace std;
 
// Function to sort an array using Selection Sort algorithm
void selectionSort(int array[], int size)
{
    int i, j, min;
 
    // Loop through the array
    for (i = 0; i < size - 1; i++)
    {
        // Find the minimum element in the array
        min = i;
        for (j = i + 1; j < size; j++)
        {
            if (array[min] > array[j])
            {
                min = j;
            }
        }
 
        // Swap the minimum element with the current element
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}
 
// Driver function
int main()
{
    // Array to be sorted
    int array[] = {5, 2, 1, 4, 3};
 
    // Size of the array
    int size = sizeof(array) / sizeof(array[0]);
 
    // Sort the array
    selectionSort(array, size);
 
    // Print the sorted array
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
 
    return 0;
}

// Output
// 1 2 3 4 5

As we can see, the Selection Sort algorithm is fairly straightforward and easy to understand.

Time Complexity of Selection Sort

The time complexity of Selection Sort is O(n²). This means that the algorithm takes O(n²) comparisons to sort an array of n elements. The best-case time complexity of Selection Sort is also O(n²). This occurs when the array is already sorted or nearly sorted. The average-case time complexity of Selection Sort is also O(n²). This occurs when the elements in the array are distributed randomly. The worst-case time complexity of Selection Sort is also O(n²). This occurs when the array is sorted in reverse order.

Space Complexity of Selection Sort

The space complexity of Selection Sort is O(1). This means that the algorithm does not require any additional space for sorting an array of n elements.

Conclusion

In this article, we discussed Selection Sort, an in-place comparison sorting algorithm. We discussed its time complexity and space complexity, and we provided a code example to illustrate how it works. Selection Sort is a simple and straightforward algorithm that runs in O(n²) time and O(1) space.

Exercises

Write a C++ program to sort an array of 10 integers using Selection Sort.

#include <iostream>
using namespace std;
 
// Function to sort an array using Selection Sort algorithm
void selectionSort(int array[], int size)
{
    int i, j, min;
 
    // Loop through the array
    for (i = 0; i < size - 1; i++)
    {
        // Find the minimum element in the array
        min = i;
        for (j = i + 1; j < size; j++)
        {
            if (array[min] > array[j])
            {
                min = j;
            }
        }
 
        // Swap the minimum element with the current element
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}
 
// Driver function
int main()
{
    // Array to be sorted
    int array[] = {5, 2, 6, 1, 9, 8, 3, 4, 7, 10};
 
    // Size of the array
    int size = sizeof(array) / sizeof(array[0]);
 
    // Sort the array
    selectionSort(array, size);
 
    // Print the sorted array
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
 
    return 0;
}

// Output
// 1 2 3 4 5 6 7 8 9 10

Write a C++ program to sort an array of characters using Selection Sort.

#include <iostream>
using namespace std;
 
// Function to sort an array using Selection Sort algorithm
void selectionSort(char array[], int size)
{
    int i, j, min;
 
    // Loop through the array
    for (i = 0; i < size - 1; i++)
    {
        // Find the minimum element in the array
        min = i;
        for (j = i + 1; j < size; j++)
        {
            if (array[min] > array[j])
            {
                min = j;
            }
        }
 
        // Swap the minimum element with the current element
        char temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}
 
// Driver function
int main()
{
    // Array to be sorted
    char array[] = {'d', 'a', 'g', 'c', 'f', 'b', 'e'};
 
    // Size of the array
    int size = sizeof(array) / sizeof(array[0]);
 
    // Sort the array
    selectionSort(array, size);
 
    // Print the sorted array
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
 
    return 0;
}

// Output
// a b c d e f g

Write a C++ program to sort an array of strings using Selection Sort.

#include <iostream>
#include <string>
using namespace std;
 
// Function to sort an array using Selection Sort algorithm
void selectionSort(string array[], int size)
{
    int i, j, min;
 
    // Loop through the array
    for (i = 0; i < size - 1; i++)
    {
        // Find the minimum element in the array
        min = i;
        for (j = i + 1; j < size; j++)
        {
            if (array[min] > array[j])
            {
                min = j;
            }
        }
 
        // Swap the minimum element with the current element
        string temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}
 
// Driver function
int main()
{
    // Array to be sorted
    string array[] = {"cat", "dog", "bird", "fish", "turtle"};
 
    // Size of the array
    int size = sizeof(array) / sizeof(array[0]);
 
    // Sort the array
    selectionSort(array, size);
 
    // Print the sorted array
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
 
    return 0;
}

// Output
// bird cat dog fish turtle

Write a C++ program to sort an array of floating-point numbers using Selection Sort.

#include <iostream>
using namespace std;
 
// Function to sort an array using Selection Sort algorithm
void selectionSort(float array[], int size)
{
    int i, j, min;
 
    // Loop through the array
    for (i = 0; i < size - 1; i++)
    {
        // Find the minimum element in the array
        min = i;
        for (j = i + 1; j < size; j++)
        {
            if (array[min] > array[j])
            {
                min = j;
            }
        }
 
        // Swap the minimum element with the current element
        float temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}
 
// Driver function
int main()
{
    // Array to be sorted
    float array[] = {3.14, 6.28, 1.41, 2.82, 5.66};
 
    // Size of the array
    int size = sizeof(array) / sizeof(array[0]);
 
    // Sort the array
    selectionSort(array, size);
 
    // Print the sorted array
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
 
    return 0;
}

// Output
// 1.41 2.82 3.14 5.66 6.28

Write a C++ program to sort a linked list using Selection Sort.

#include <iostream>
using namespace std;

// Node structure
struct node {
    int data;
    node* next;
};

// Function to sort a linked list using Selection Sort algorithm
node* selectionSort(node* head)
{
    node* current = head;
    node* min = NULL;
    node* prev = NULL;

    while (current != NULL)
    {
        // Set min and prev to current node
        min = current;
        prev = current;
        node* search = current;

        while (search != NULL)
        {
            // Find the minimum node in the list
            if (search->data < min->data)
            {
                min = search;
                prev = search->next;
            }
            search = search->next;
        }

        // Swap the minimum node with the current node
        int temp = current->data;
        current->data = min->data;
        min->data = temp;

        // Move current node to the next
        current = current->next;
    }
    return head;
}

// Utility function to print the linked list
void printList(node* head)
{
    while (head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// Driver function
int main()
{
    // Create a linked list
    node* head = NULL;
    head = new node;
    head->data = 5;
    head->next = new node;
    head->next->data = 2;
    head->next->next = new node;
    head->next->next->data = 1;
    head->next->next->next = new node;
    head->next->next->next->data = 4;
    head->next->next->next->next = new node;
    head->next->next->next->next->data = 3;

    // Print the unsorted linked list
    cout << "Unsorted list: ";
    printList(head);

    // Sort the linked list
    head = selectionSort(head);

    // Print the sorted linked list
    cout << "Sorted list:   ";
    printList(head);

    return 0;
}

// Output
// Unsorted list: 5 2 1 4 3 
// Sorted list:   1 2 3 4 5