Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    7 Radix Sort

    Uploaded by

    Banwari Lal Meena Lalsot
    The document describes the Radix Sort algorithm. It begins by explaining the theory behind Radix Sort, which involves sorting strings into piles based on their first letters, then recursively sorting the piles based on subsequent letters. It then provides pseudocode for implementing Radix Sort on an integer list. The algorithm has a worst-case time complexity of O(k*n) where k is the length of the longest value and n is the length of the array. Finally, the document provides an example C program that implements Radix Sort and sample input/output.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd

    7 Radix Sort

    Uploaded by

    Banwari Lal Meena Lalsot
    32 views4 pages
    The document describes the Radix Sort algorithm. It begins by explaining the theory behind Radix Sort, which involves sorting strings into piles based on their first letters, then recursively sorting the piles based on subsequent letters. It then provides pseudocode for implementing Radix Sort on an integer list. The algorithm has a worst-case time complexity of O(k*n) where k is the length of the longest value and n is the length of the array. Finally, the document provides an example C program that implements Radix Sort and sample input/output.

    Original Description:

    7 radix

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the Radix Sort algorithm. It begins by explaining the theory behind Radix Sort, which involves sorting strings into piles based on their first letters, then recursively sorting the piles based on subsequent letters. It then provides pseudocode for implementing Radix Sort on an integer list. The algorithm has a worst-case time complexity of O(k*n) where k is the length of the longest value and n is the length of the array. Finally, the document provides an example C program that implements Radix Sort and sample input/output.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    32 views4 pages

    7 Radix Sort

    Uploaded by

    Banwari Lal Meena Lalsot
    The document describes the Radix Sort algorithm. It begins by explaining the theory behind Radix Sort, which involves sorting strings into piles based on their first letters, then recursively sorting the piles based on subsequent letters. It then provides pseudocode for implementing Radix Sort on an integer list. The algorithm has a worst-case time complexity of O(k*n) where k is the length of the longest value and n is the length of the array. Finally, the document provides an example C program that implements Radix Sort and sample input/output.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 4

    Program 7

    AIM:- Wap to implement of RADIX SORT THEORY:Deal the strings into piles by their first letters. One pile gets all the empty strings. The next gets all the strings that begin with A-; another gets Bstrings, and so on. Split these piles recursively on second and further letters until the strings end. When there are no more piles to split, pick up all the piles in order. The strings are sorted.

    ALGORITHM:radix_sort(list[n], n) 1) b[n] , exp 1 , max (maximum element of list) 2) while max/exp>0 repeat step 3 to 13 3) box[10] {0} 4) for i= 0 to n-1 repeat step 5 5) box[a[i]/exp%10]++ 6) for i=1 to 9 repeat step 7 7) box[i]+=box[i-1] 8) for i=n-1 to 1 repeat step 9 9) b[--box[a[i] / exp % 10]] = a[i] 10) for i=0 to n repeat step 11 11) a[i]=b[i] 13) exp*=10 14) end of while 15) return list 16) end Radix

    COMPLEXITY:The worse case complexity of MSD radix sort is O(k*n) where

    k = "length of the longest value in Array to be sorted" n = "length of the array"


    k * n = n^2 (if k = n) so when using Radix sort make sure "the longest integer is shorter than the array size" or vice versa. Then you going to beat Quicksort.

    APPLICATIONS:Radix Sort correctly handles floating-point values, there are tons of ways to use it in Computer Graphics. Here are two obvious examples : 1. 2. Sorting transparent polygons Collision detection betewwngraphics designs

    PROGRAM :
    #include <stdio.h> #include<conio.h> #define MAX 100 void print(int *a, int n) { int i; for (i = 0; i < n; i++) printf("%d\t", a[i]); } void radix_sort(int *a, int n) { int i, b[MAX], m = 0, exp = 1; for (i = 0; i < n; i++) { if (a[i] > m) m = a[i]; }

    while (m / exp > 0) { int box[10] = { 0 }; for (i = 0; i < n; i++) box[a[i] / exp % 10]++; for (i = 1; i < 10; i++)

    box[i] += box[i - 1]; for (i = n - 1; i >= 0; i--) b[--box[a[i] / exp % 10]] = a[i]; for (i = 0; i < n; i++) a[i] = b[i]; exp *= 10; printf("\n\nPASS : "); print(a, n); } }

    int main() { int arr[MAX]; int i, num; clrscr(); printf("\nEnter total elements (num < %d) : ", MAX); scanf("%d", &num);

    printf("\nEnter %d Elements : ", num); for (i = 0; i < num; i++) scanf("%d", &arr[i]); printf("\nARRAY : "); print(&arr[0], num); radix_sort(&arr[0], num);

    printf("\n\nSORTED : "); print(&arr[0], num); getch(); return 0; }

    OUTPUT

    You might also like