Bubble Сортировать используя Bubble Up

Question

Учитывая алгоритм пузырьковой сортировки:

Algorithm BubbleSort(A[0...n]): 
    for i <- 0 to n-2 do 
    for j <- 0 to n-2-i do 
     if(A[j+1] < A[j] then swap(A[j], A[j+1])) 

Я должен переписать алгоритм пузырьковой сортировки с помощью которой мы «Bubble Up» наименьший элемент в положение го на г-й пройти через список.

Может ли кто-нибудь помочь мне с этим?

Answer 1

В настоящее время вы перемещаете массив с самого начала, поэтому, если вы попадаете на самый большой элемент, он будет «Bubbled up» до конца массива. Если вы хотите сделать обратное, «Bubbling down» наименьший элемент до начала, вам нужно пройти массив в противоположном направлении, от конца до начала. Надеюсь, это поможет вам найти путь.

Answer 2

#include<stdio.h> 
void bubbleSort(int *x,int size) 
{ 
    int e,f,m,g; 
    m=size-2; 
    while(m>0) 
    { 
    e=0; 
    f=1; 
    while(e<=m) 
    { 
     if(x[f]<x[e]) 
     { 
     g=x[e];  //swaping 
     x[e]=x[f]; 
     x[f]=g; 
     } 
    e++; 
    f++; 
    } 
    m--; 
    } 
} 
void main() 
{ 
    int x[10],y; 
    for(y=0;y<=9;y++)  //loop to insert 10 numbers into an array 
    { 
    printf("Enter a number: "); 
    scanf("%d",&x[y]); 
    } 
    bubbleSort(x,10);  //pass number entered by user and size of array to bubbleSort 
    for(y=0;y<=9;y++)  //loop to print sorted numbers 
    { 
    printf("%d\n",x[y]); 
    } 
} 

Answer 3

Похоже, что ответ на этот вопрос еще не принят. Поэтому пытаюсь проверить, не является ли это проблемой.

Вот что, по моему мнению, может быть возможной реализацией на Java. Как отметил @Warlord, алгоритм должен гарантировать, что массив, вызывающий озабоченность при сортировке, представлен как вертикальный массив. С каждым проходом все, что мы делаем, это проверить, есть ли более крупный элемент ниже, и если обнаружено, что элемент пузырится вверх.

static void bubbleUpSort(int[] arr){ 
    final int N = arr.length; 
    int tmp = 0; 
    for (int i=0; i < N; i++){ 
     for (int j=N-1; j >= i+1; j--){ 
      if (arr[j] < arr[j-1]){ 
       tmp = arr[j]; 
       arr[j] = arr[j-1]; 
       arr[j-1] = tmp; 
      } 
     } 
    } 

    for (int k =0; k < arr.length; k++){ 
     System.out.print(arr[k] + " "); 
    } 
} 

Вызывается из главного как:

public static void main(String[] args) { 
    System.out.println("Bubble Up Sort"); 
    int[] bUp = {19, 2, 9, 4, 7, 12, 13, 3, 6}; 
    bubbleUpSort(bUp); 
}