Showing posts with label Selection Sort Algorithm. Show all posts
Showing posts with label Selection Sort Algorithm. Show all posts

Thursday, May 7, 2020

Selection sort algorithm And Its Examples

 This Chapter will help to learn about Selection sort algorithm And Its Examples inmany languages like python, c, Java.

 
Selection sort algorithm And Its Examples
Selection sort algorithm And Its Examples


Selection sort algorithm न्यूनतम या अधिकतम Element को अनसोल्ड Array में खोजने और फिर Sort किए गए एरे में अपनी सही स्थिति में रखने के विचार पर आधारित है।

Let Assume An array A[7,5,4,2] Ascending order में क्रमबद्ध करने की आवश्यकता है।

सरणी में न्यूनतम Element अर्थात् 2 के लिए खोज की जाती है और फिर उस Element से बदली जाती है जो वर्तमान में पहली स्थिति में स्थित है, अर्थात 7 अब remaining unsorted array  में न्यूनतम तत्व को दूसरे स्थान पर खोजा जाता है, और इसी तरह आगे भी।

Steps For Selection sort algorithm  

void selection_sort (int A[ ], int n) {
        // temporary variable to store the position of minimum element

        int minimum;        
        // reduces the effective size of the array by one in  each iteration.

        for(int i = 0; i < n-1 ; i++)  {

           // assuming the first element to be the minimum of the unsorted array .
             minimum = i ;

          // gives the effective size of the unsorted  array .

            for(int j = i+1; j < n ; j++ ) {
                if(A[ j ] < A[ minimum ])  {                //finds the minimum element
                minimum = j ;
                }
             }
          // putting minimum element on its proper position.
          swap ( A[ minimum ], A[ i ]) ; 
        }
   }
At ith iteration, elements from position 0 to i-1 will be sorted.
"Selection sort algorithm"
"Selection sort algorithm"


 Time Complexity For Selection sort algorithm 

element from the array N से न्यूनतम तत्व को खोजने के लिए,N-1 तुलना की आवश्यकता होती है। न्यूनतम तत्व को उसकी उचित स्थिति में रखने के बाद, एक Unsorted Array का आकार N-1 कम हो जाता है और फिर N-2 Unsorted Array में न्यूनतम खोजने के लिए तुलना की आवश्यकता होती है। 

Therefor (N-1)+(N-2)+.........+1 = (N.(N-1))/2  comparisons and N swaps result in the overall O(N^2) complexity of .  

  • Selection Sort Program In C ++


// C++ program for implementation of selection sort  
#include  
using namespace std; 
  
void swap(int *xp, int *yp)  
{  
    int temp = *xp;  
    *xp = *yp;  
    *yp = temp;  
}  
  
void selectionSort(int arr[], int n)  
{  
    int i, j, min_idx;  
  
    // One by one move boundary of unsorted subarray  
    for (i = 0; i < n-1; i++)  
    {  
        // Find the minimum element in unsorted array  
        min_idx = i;  
        for (j = i+1; j < n; j++)  
        if (arr[j] < arr[min_idx])  
            min_idx = j;  
  
        // Swap the found minimum element with the first element  
        swap(&arr[min_idx], &arr[i]);  
    }  
}  
  
/* Function to print an array */
void printArray(int arr[], int size)  
{  
    int i;  
    for (i=0; i < size; i++)  
        cout << arr[i] << " ";  
    cout << endl;  
}  
  
// Driver program to test above functions  
int main()  
{  
    int arr[] = {64, 25, 12, 22, 11};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    selectionSort(arr, n);  
    cout << "Sorted array: \n";  
    printArray(arr, n);  
    return 0;  
}

  •  Selection Sort Program In Python


# Python program for implementation of Selection 
# Sort 
import sys 
A = [64, 25, 12, 22, 11] 
  
# Traverse through all array elements 
for i in range(len(A)): 
      
    # Find the minimum element in remaining  
    # unsorted array 
    min_idx = i 
    for j in range(i+1, len(A)): 
        if A[min_idx] > A[j]: 
            min_idx = j 
              
    # Swap the found minimum element with  
    # the first element         
    A[i], A[min_idx] = A[min_idx], A[i] 
  
# Driver code to test above 
print ("Sorted array") 
for i in range(len(A)): 
    print("%d" %A[i]),  
  • Selection Sort Program In C

// C program for implementation of selection sort 
#include  
  
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 
  
void selectionSort(int arr[], int n) 
{ 
    int i, j, min_idx; 
  
    // One by one move boundary of unsorted subarray 
    for (i = 0; i < n-1; i++) 
    { 
        // Find the minimum element in unsorted array 
        min_idx = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] < arr[min_idx]) 
            min_idx = j; 
  
        // Swap the found minimum element with the first element 
        swap(&arr[min_idx], &arr[i]); 
    } 
} 
  
/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {64, 25, 12, 22, 11}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    selectionSort(arr, n); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
} 
  • Selection Sort Program In Java

class SelectionSort
{
    void sort(int arr[])
    {
        int n = arr.length;
  
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
  
            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
  
    // Prints the array
    void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
  
    // Driver code to test above
    public static void main(String args[])
    {
        SelectionSort ob = new SelectionSort();
        int arr[] = {64,25,12,22,11};
        ob.sort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }
}

Sorting Algorithm : - 

Bubble Sort Algorithm And sorting program in different language

bucket sort Algorithm In Hindi And Its Examples

Counting sort Algorithm in hindi and Its Example 

Heap Sort Algorithm In Hindi and its examples 

Insertion sort Algorithm And Its Examples

Merge Sort Algorithm In HIndi And Its Examples

Quick Sort Algorithm And Its Examples in hindi