Quantcast
Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
    1. Welcome to GTAForums!   (84,988 visits to this link)

    2. News

    1. GTA Online

      1. Find Lobbies & Players
      2. Guides & Strategies
      3. Vehicles
      4. Content Creator
      5. Help & Support
    2. Crews

      1. Events
      2. Recruitment
    1. Grand Theft Auto Series

    2. GTA Next

    3. GTA V

      1. PC
      2. Guides & Strategies
      3. Help & Support
    4. GTA IV

      1. Episodes from Liberty City
      2. Multiplayer
      3. Guides & Strategies
      4. Help & Support
      5. GTA Mods
    5. GTA Chinatown Wars

    6. GTA Vice City Stories

    7. GTA Liberty City Stories

    8. GTA San Andreas

      1. Guides & Strategies
      2. Help & Support
      3. GTA Mods
    9. GTA Vice City

      1. Guides & Strategies
      2. Help & Support
      3. GTA Mods
    10. GTA III

      1. Guides & Strategies
      2. Help & Support
      3. GTA Mods
    11. Top Down Games

      1. GTA Advance
      2. GTA 2
      3. GTA
    12. Wiki

      1. Merchandising
    1. GTA Modding

      1. GTA V
      2. GTA IV
      3. GTA III, VC & SA
      4. Tutorials
    2. Mod Showroom

      1. Scripts & Plugins
      2. Maps
      3. Total Conversions
      4. Vehicles
      5. Textures
      6. Characters
      7. Tools
      8. Other
      9. Workshop
    3. Featured Mods

      1. DYOM
      2. OpenIV
      3. GTA: Underground
      4. GTA: Liberty City
      5. GTA: State of Liberty
    1. Red Dead Redemption 2

    2. Red Dead Redemption

    3. Rockstar Games

    1. Off-Topic

      1. General Chat
      2. Gaming
      3. Technology
      4. Programming
      5. Movies & TV
      6. Music
      7. Sports
      8. Vehicles
    2. Expression

      1. Graphics / Visual Arts
      2. GFX Requests & Tutorials
      3. Writers' Discussion
      4. Debates & Discussion
    1. Forum Support

    2. Site Suggestions

Sign in to follow this  
coin-god

Help with some algoritms

Recommended Posts

coin-god

I have to write a function in JAVA that modifies an array by using the first element as a pivot and moves all the elements that are smaller to it's left and the ones bigger to it's right. I have to use crossed recursion. The pivot is compared to each of the other elements only once.

 

Example:

 

3 4 1 8 6 5 2

 

Should end up like this (I think):

 

1 2 3 4 8 6 5 (3 is pivot)

 

I guess the actual order of the smaller/bigger elements dosn't matter.

I honestly have no idea of were to start. They didn't give use much information about how to do this kind of stuff in college.

This is not "homework", I'm studing for my final exam.

Share this post


Link to post
Share on other sites
K^2

Are you sure you are supposed to use recursion for pivoting? This is part of the quick sort algorithm, which indeed, is done recursively. You could make even the pivot recursive, but I don't see why you'd want to. There are several ways of doing this. The most typical actually used by quick sort would proceed like this.

 

 

Indecies of two pointers start at two ends of array, excluding pivot.3 4 1 8 6 5 2 One on the left is > pivot, while right < pivot. Swap.* ^         ^3 2 1 8 6 5 4 Left pointer is < pivot, so pointer is advanced. Right > pivot, advanced.* ^         ^3 2 1 8 6 5 4 Again, both are correct, so both are advanced.*   ^     ^3 2 1 8 6 5 4 Left pointer > pivot. Right > pivot. Left stays, right advances.*     ^ ^3 2 1 8 6 5 4 Pointers merged. Now we need to step back, and swap with pivot.*     ^3 2 1 8 6 5 4 Perform swap.^   ^1 2 3 8 6 5 4 Final state. To do full quick sort, repeat with 1 and 8 as pivots, etc.

 

 

Code for it would look something like this. (C syntax)

 

 

a=1;b=length-1;while(a!=b){  if(array[a]<array[0]){a++; continue;}  if(array[b]>array[0]){b--; continue;}  swap(array+a, array+b);}swap(array, array+a-1);

 

 

If you insist on this part being done recursively, you can make it run something along the lines of this.

 

 

void pivot(int array[], int a, int b){   if(a==b){swap(array, array+a-1);return;}   if(array[a]<array[0]){pivot(array,a+1,b); return;}   if(array[b]>array[0]){pivot(array,a,b-1); return;}   swap(array+a, array+b);   pivot(array,a,b);}pivot(array, 1, length-1);

 

 

But honestly, that's just a waste of stack space and jump instructions.

 

Full quick sort written to implement the first form with recursion would be written like this.

 

void quicksort(int array[], int length){   if(length<=1)return;   a=1;   b=length-1;   while(a!=b)   {     if(array[a]<array[0]){a++; continue;}     if(array[b]>array[0]){b--; continue;}     swap(array+a, array+b);   }   swap(array, array+a-1);   quicksort(array, a-1);   quicksort(array+a,length-a);}

 

Edited by K^2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using GTAForums.com, you agree to our Terms of Use and Privacy Policy.