Results 1 to 5 of 5

Thread: Explain this code

  1. #1
    girldemsuga Guest

    Default Explain this code

    I need some help, could someone explain the code below

    I know it is implementing a select sort, but I can see why 2 for loops are needed. Please explain.

    Code:
           void  selectionSort(int arr[], int len){
              int i;
              int j;
              int temp;
              int pos_greatest;
    
              for( i = len - 1; i > 0; i--){
                 pos_greatest = 0;
                 for(j = 0; j <= i; j++){
                    if( arr[j] > arr[pos_greatest]){
                       pos_greatest =  j;
                    }//end if
                 }//end inner for loop
                 temp = arr[i];
                 arr[i] = arr[pos_greatest];
                 arr[pos_greatest] = temp;
              }//end outer for loop
           }//end selection sort

  2. #2
    Join Date
    Jan 2009
    Posts
    2,404
    Rep Power
    0

    Default

    The inner loop (counting from the first element in the array up to the element specified by the outer loop) is ensuring that 'pos_greatest' contains the position of the greatest number in the current selection (between 'len' - 1 and 0) of 'arr'. The outer loop, counting from the end of the array to the start, takes the greatest value (found with the inner loop using 'pos_greatest') and swaps it with wherever 'i' points to in 'arr'.
    Rooted OnePlus 2 64GB Ed, Android 5.1.1 OxygenOS ; on teifin' AT&T's network; Rooted ASUS Transformer TF101 w/ dock, Android 5.1 KatKiss; Laptop: ASUS X550C, 2.0GHzx2, 8GB, 512GB SSD, Kubuntu 15.10;
    Facebook page: Skeleville Technology Solutions

  3. #3
    Join Date
    Apr 2008
    Posts
    1,245
    Rep Power
    0

    Default

    it needs 2 loops because one loop passes through the other, it looks like the array is ascending, in every pass through the inner loop the largest element i think we will see is (0-i), the outer loop seems to swap element to position (i) and gradually decreases (i)

    skele drew is correct,

    now i remember why i hated school

  4. #4
    Join Date
    Dec 2002
    Posts
    500
    Rep Power
    0

    Default

    its a divide and conquer: we start with 2 imaginary lists [unsorted]|[sorted]
    unsorted contains all the element, and sorted is empty.

    the inner loops simply finds the largest (select) from unsorted
    the outer loop then
    1. removes it
    2. puts it in the sorted side,
    3. makes the unsorted-side shorter by one element.

    by making the unsorted list shorter, we ensure that there will be a point when we dont need to find (select) the largest... when the list has 1 or less items.
    Cultured in Aggression and Koding like a Warrior!!
    “Common sense is instinct. Enough of it is genius.” - George Bernard Shaw.
    "The significant problems we face cannot be solved by the same level of thinking that created them." - Albert Einstein

  5. #5
    girldemsuga Guest

    Default

    Quote Originally Posted by icymint3 View Post
    its a divide and conquer: we start with 2 imaginary lists [unsorted]|[sorted]
    unsorted contains all the element, and sorted is empty.

    the inner loops simply finds the largest (select) from unsorted
    the outer loop then
    1. removes it
    2. puts it in the sorted side,
    3. makes the unsorted-side shorter by one element.

    by making the unsorted list shorter, we ensure that there will be a point when we dont need to find (select) the largest... when the list has 1 or less items.
    Thank you for the reply.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •