Оптимизированная пузырьковая сортировка (Java)
Я хотел бы знать, как еще можно оптимизировать пузырьковую сортировку, чтобы она пропускала элементы, которые уже были отсортированы, даже после первого прохода.
Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]
Мы видим, что [4,5,6] уже в отсортированном порядке, как можно изменить мой код, чтобы он пропустил эти 3 элемента в следующем проходе? (что означает, что сортировка будет более эффективной?) Вы предлагаете рекурсивный метод?
public static void bubblesort(int[] a) {
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
for(int j=0; j<a.length; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
}
}
if(is_sorted) return;
}
}
Спасибо за ваше время!
12 ответов
Прежде всего, у вас есть доступ за пределы:
for(int j=0; j<a.length; j++) {
if(a[j] > a[j+1]) {
за j == a.length-1поэтому условие цикла должно быть j < a.length-1,
Но в Bubble, вы знаете, что после k проходит, самый большой k элементы отсортированы на k последние записи массива, поэтому обычная сортировка Bubble использует
public static void bubblesort(int[] a) {
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
}
}
if(is_sorted) return;
}
}
Теперь, это все еще будет делать много ненужных итераций, когда массив имеет длинный отсортированный хвост самых больших элементов, скажем, у вас есть k,k-1,...,1 как первый k элементы и k+1 в 100000000 после этого. Стандартный пузырьковый сорт пройдет k раз через (почти) весь массив.
Но если вы помните, где вы сделали свой последний обмен, вы знаете, что после этого индекса расположены самые крупные элементы в порядке, поэтому
public static void bubblesort(int[] a) {
int lastSwap = a.length-1;
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
int currentSwap = -1;
for(int j=0; j < lastSwap; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
currentSwap = j;
}
}
if(is_sorted) return;
lastSwap = currentSwap;
}
}
отсортировал бы приведенный выше пример только с одним проходом через весь массив, а остальные проходили только через (короткий) префикс.
Конечно, в общем, это не будет вам дорого, но тогда оптимизация типа Bubble - это довольно бесполезное занятие.
public static Integer[] optimizedbubbleSort(Integer[] input){
long startTime = System.nanoTime();
boolean swapped = true;
for(int pass=input.length-1; pass>=0 && swapped; pass--){
swapped = false;
for(int i=0; i<pass; i++){
if(input[i]>input[i+1]){
int temp = input[i];
input[i] = input[i+1];
input[i+1] = temp;
swapped = true;
}
}
}
System.out.println("Time taken for OPTIMIZED bubbleSort: "+(System.nanoTime() - startTime));
return input;
}
Вы должны использовать переменную "size" для внутреннего цикла и заменять ее на последний замененный элемент в каждом цикле. Таким образом, ваш внутренний цикл поднимается до самого последнего "замененного" элемента и пропускает остальные, которые не были поменены местами (иначе говоря, в их правильном месте).). т.е.
do {
int newsize =0;
for (int i = 1; i < size; i++) {
if (a[i - 1] > a[i]) {
int temp;
temp = a[i - 1];
a[i - 1] = a[i];
a[i] = temp;
newsize =i;
}
}
size = newsize;
} while (size > 0);
public static void BubbleSorter(params int[] input){
int newSize = input.Length-1, size = 0;
bool swap;
do
{
swap = false;
for (int j = 0; j < newSize; j++)
{
if (input[j] > input[j + 1])
{
int temp = input[j + 1];
input[j + 1] = input[j];
input[j] = temp;
swap = true;
size = j;
}
} newSize = size;
} while (swap);
DisplayArrayElements(input);
}
Вот самый простой, лучший и оптимальный алгоритм пузырьковой сортировки с использованием цикла while. Он сортирует числа в заданной форме массива слева направо в порядке возрастания. Это очень просто понять и легко реализовать.
private static int[] bubbleSort(int[] array) {
int length = array.length - 1;
int index = 0;
while ( index < length) {
if (array[index] > array[index + 1]) {
swap(array, index, index + 1);
}
index++;
if (index == length) {
index = 0;
length--;
}
}
return array;
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
Вы можете использовать один цикл do-while вместо двух вложенных циклов for и переместить логику во внутренний оператор if. Последующие проходы короче на индекс прохода.
public static void bubbleSort(int[] arr) {
boolean swapped = false;
int i = 0, pass = 0;
do {
if (i < arr.length - 1 - pass) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
i++;
} else {
i = 0;
pass++;
swapped = false;
}
} while (i < arr.length - 1 - pass || swapped);
}
public static void main(String[] args) {
int[] arr = {6, 1, 5, 8, 4, 3, 9, 2, 0, 7};
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
Выход:
[6, 1, 5, 8, 4, 3, 9, 2, 0, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
См. Также: Неверный вывод пузырьковой сортировки
В приведенном выше примере массив отсортирован после 3-го прохода, но мы все равно продолжим с 4-го, 5-го прохода. Предположим, что если массив уже отсортирован, то перестановки не будет (потому что соседние элементы всегда в порядке), но мы все равно продолжим проходы, и все равно будет (n-1) проходов.
Если мы можем определить, что массив отсортирован, то мы должны остановить выполнение дальнейших проходов. Это оптимизация по сравнению с оригинальным алгоритмом сортировки пузырьков.
Если в конкретном проходе нет перестановки, это означает, что массив отсортирован, поэтому мы не должны выполнять дальнейшие проходы. Для этого у нас может быть переменная флага, которая устанавливается в true перед каждым проходом и становится ложной, когда выполняется свопинг.
void bubbleSort(int *arr, int n){
for(int i=0; i<n; i++)
{
bool flag = false;
for(int j=0; j<n-i-1; j++)
{
if(array[j]>array[j+1])
{
flag = true;
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
// No Swapping happened, array is sorted
if(!flag){
return;
}}}
public class Tester {
static boolean bubbleFlag = true;
public static void main(String[] args) {
int array[] = new int[] {
1,
9,
2,
3,
4,
5,
6
};
bubbleSort(array);
}
private static void bubbleSort(int...array) {
System.out.println("Before Sorting: " + Arrays.toString(array));
for (int i = 0; i < array.length - 1; i++) {
if (i > 0) if (bubbleFlag) break;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) array = swap(j, j + 1, array);
System.out.println("Iteration " + i + " :" + Arrays.toString(array));
}
bubbleFlag = true;
}
}
private static int[] swap(int i1, int i2, int...is) {
bubbleFlag = false;
is[i1] = is[i1] + is[i2];
is[i2] = is[i1] - is[i2];
is[i1] = is[i1] - is[i2];
return is;
}
}
Я разработал метод, который уменьшает количество итераций, исключая части в начале и конце массива, которые были упорядочены в предыдущих циклах.
static int[] BubbleSortOptimized(int arr[]) {
int start = 0, stop = arr.length - 1, control = 0;
boolean ordered, nsCaught;
while (true){
ordered = true;
nsCaught = false;
for (int i = start; i < stop; i++) {
if (i > 1) {
if (!nsCaught && arr[i-2] > arr[i-1]){
ordered = false;
start = i-2;
nsCaught = true;
}
}
if (arr[i] > arr[i+1]){
int hold = arr[i];
arr[i] = arr[i+1];
arr[i+1] = hold;
control = i;
}
}
System.out.println(Arrays.toString(arr));
if (ordered) return arr;
stop = control;
}
}
Но, как сказал @Daniel Fischer в предыдущем ответе, с большими массивами это мало что дает.
Думаю, это то, что вам нужно. Ключ заключается в том, чтобы рассматривать массив только до индекса, в котором произошла последняя замена (newn).
public static void bubblesort(int[] a) {
int i, n, newn;
n = a.length;
while (n > 0) {
newn = 0;
for (i = 1; i < n; i++) {
if (a[i - 1] > a[i]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
newn = i;
}
}
n = newn;
}
return a;
}
У меня нет кода, но вы можете использовать n бит, чтобы отслеживать, где были выполнены свопы на последнем проходе. Или, что менее эффективно, используйте одну переменную, чтобы отслеживать, где была произведена первая замена. Нам не нужно повторно сравнивать элементы, которые не были заменены местами - это одни и те же элементы в том же порядке, поэтому мы знаем, что сравнения будут такими же, и можем безопасно их пропустить.
Интуитивно я чувствую, что даже с указанной выше оптимизацией пузырьковая сортировка все равно не превзойдет сравнения двоичной сортировки вставкой и внесет гораздо больше логики ветвления (поверх вспомогательного пространства) для отслеживания свопов. Так что это, вероятно, не стоит исследовать, если кому-то не интересно.
Оптимизированная сортировка пузырьков с помощью только 1 для цикла
/*Advanced BUBBLE SORT with ONE PASS*/
/*Authored by :: Brooks Tare AAU*/
public class Bubble {
public int[] bubble(int b[]){
int temp,temp1;
for(int i=0;i<b.length-1;i++){
if(b[i]>b[i+1] ){
///swap(b[i],b[i+1]);
temp=b[i];
b[i]=b[i+1];
b[i+1]=temp;
/*Checking if there is any number(s) greater than
the current number. If there is swap them.*/
while(i>0){
if(b[i]<b[i-1]){
///swap(b[i]<b[i-1])
temp1=b[i];
b[i]=b[i-1];
b[i-1]=temp1;
i--;
}
else if(b[i]>b[i-1]){i--;}
}
}
else{continue;}
}
return b;
}
///the following is a function to display the Array
public void see(int []a){
for(int j=0;j<a.length;j++){
System.out.print(a[j]+",");
}
}
public static void main(String []args){
///You can change the Array to your preference.. u can even make it dynamic
int b[]={5,1,4,2,0,3};
int v[]=new int[100];
Bubble br=new Bubble();
v=br.bubble(b);
br.see(v);
}
}